Target Sum

wind3110991 发布于2019-08-14 17:22 / 2069人阅读

摘要：题目链接，可以，不过这题可以，所以可以用做或者来做，还是得用二维数组保存算过的结果。这题的是到第个数时，能够得到为的数量，由于可能是负数，所以要做一个，使其从开始。滚动数组优化空间。

Target Sum

题目链接：https://leetcode.com/problems...

dp，可以brute force，不过这题可以memory，所以可以iteration用dp table做或者recursion：dfs+suffix array来做，还是得用二维数组保存算过的结果。这题的subproblem是到第i个数时，能够得到sum为j的ways数量，由于sum可能是负数，所以要做一个shift，使其从0开始。滚动数组优化空间。

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        if(nums == null || nums.length == 0) return 0;
        // dp table
        int sum = 0;
        for(int num : nums) sum += num;
        if(S > sum || S < -sum) return 0;
        // dp[i][j]: the number of ways that add up to j using [0, i]
        // function: dp[i+1][j - nums[i]] = dp[i][j]
        //           dp[i+1][j + nums[i]] = dp[i][j]
        // j = [0, 2 * sum + 1]
        int[] dp = new int[2*sum + 1];
        dp[0+sum] = 1;
        for(int i = 0; i < nums.length; i++) {
            int[] next = new int[2*sum + 1];
            for(int j = 0; j < 2 * sum + 1; j++) {
                if(j - nums[i] >= 0 && dp[j] != 0) next[j-nums[i]] += dp[j];
                if(j + nums[i] < 2 * sum + 1 && dp[j] != 0) next[j+nums[i]] += dp[j];
            }
            dp = next.clone();
        }
        return dp[0 + sum + S];
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66595.html

[Leetcode] 3Sum 4Sum 3Sum Closet 多数和

摘要：为了避免得到重复结果，我们不仅要跳过重复元素，而且要保证找的范围要是在我们最先选定的那个数之后的。而计算则同样是先选一个数，然后再剩下的数中计算。 2Sum 在分析多数和之前，请先看Two Sum的详解 3Sum 请参阅：https://yanjia.me/zh/2019/01/... 双指针法复杂度时间 O(N^2) 空间 O(1) 思路 3Sum其实可以转化成一个2Sum的题，...

trigkit4 2019-08-14 12:29 评论0 收藏0
【LC总结】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合条件的总数。双指针区间考虑边界，长度，为空，等。之后的范围用双指针和表示。若三个指针的数字之和为，加入结果数组。不要求，所以不用判断了。同理，头部两个指针向后推移，后面建立左右指针夹逼，找到四指针和为目标值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

awesome23 2019-08-14 15:50 评论0 收藏0
Leetcode 题解 - 双指针

摘要：一有序数组的题目描述在有序数组中找出两个数，使它们的和为。解题思路使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。输出二两数平方和判断一个数是否为数平方和开平方根一、有序数组的 Two Sum Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 题目描述：在有序数组中找出两个数，使它们...

leanxi 2019-08-16 18:40 评论0 收藏0
leetcode14 4sum

摘要：这里需要注意及时处理掉重复的情况。那么就需要尽可能排除不可能的情况来提高计算效率。因为数组已经被排序，所以可以根据数组中元素的位置判断接下来的情况是否有可能合成目标值。题目要求此处为原题地址 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d =...

MoAir 2019-08-16 10:31 评论0 收藏0
[LeetCode] 416. Partition Equal Subset Sum

Problem Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:Each of the array ...

makeFoxPlay 2019-08-16 13:42 评论0 收藏0
leetcode494. Target Sum

摘要：为了寻找合适的正负号赋值，我们其实可以将数组分为两个子集，其中一个子集中的数字都被赋予了正号，而另一个子集中的数字都被赋予了负号。如果二者的和不是一个偶数，就一定无法找到这样的正负号集合使得其结果为。题目要求 You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now yo...

RobinTang 2019-08-15 14:32 评论0 收藏0