## LeetCode 494解题思路 原

爱喝冰可乐

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols `+` and `-`. For each integer, you should choose one from `+` and `-` as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

```Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.```

``````class Solution {
public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for (int n : nums)
sum += n;
return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1);
}

public int subsetSum(int[] nums, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
}``````

``````sum(P) - sum(N) = target

sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)

2 * sum(P) = target + sum(nums)``````

### 爱喝冰可乐

LeetCode - 014 - 最长公共前缀（longest-common-prefix）

Create by jsliang on 2019-06-03 10:13:01 Recently revised in 2019-06-03 17:29:09 为方便小伙伴们的查看，欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/04
0
0
LeetCode - 021 - 合并两个有序链表（merge-two-sorted-lists）

Create by jsliang on 2019-06-05 08:37:00 Recently revised in 2019-06-05 17:31:37 为方便小伙伴们的查看，欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/06
0
0
LeetCode - 027 - 移除元素（remove-element）

Create by jsliang on 2019-06-06 15:56:49 Recently revised in 2019-06-10 07:42:46 为方便小伙伴们的查看，欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/10
0
0
LeetCode - 007 - 整数反转（reverse-integer）

Create by jsliang on 2019-05-19 09:42:39 Recently revised in 2019-05-19 16:08:24 Hello 小伙伴们，如果觉得本文还不错，记得给个 star ， 小伙伴们的 star 是我持续更新的动力！GitHub ...

jsliang
05/19
0
0
LeetCode - 026 - 删除排序数组中的重复项（remove-duplicates-from-sorted-array）

Create by jsliang on 2019-06-06 11:11:26 Recently revised in 2019-06-06 14:30:57 为方便小伙伴们的查看，欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/07
0
0

OSChina 周六乱弹 —— 如果是个帅小伙你愿意和他出去吗

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 小小编辑推荐：《Ghost 》游戏《死亡搁浅》原声 《Ghost 》游戏（《死亡搁浅》原声） - Au/Ra / Alan Walker 手机党少年们想听歌，请使劲儿戳...

176
6
java通过ServerSocket与Socket实现通信

Blueeeeeee

6
0

5
0

16
0

（手机横屏看源码更方便） 注：java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期，但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

19
0