目标和

作者: Antrn | 来源:发表于2019-08-11 20:41 被阅读0次

    给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

    返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

    示例 1:

    输入: nums: [1, 1, 1, 1, 1], S: 3
    输出: 5
    解释:

    -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

    一共有5种方法让最终目标和为3。
    注意:

    数组的长度不会超过20,并且数组中的值全为正数。
    初始的数组的和不会超过1000。
    保证返回的最终结果为32位整数。

    C++1
    class Solution {
    public:
        int result;
        int findTargetSumWays(vector<int>& nums, int S) {
            dfs(0, 0, nums, S);
            return result;
        }
        void dfs(int sum, int cnt, vector<int>& nums, int S) {
            if(cnt == nums.size()) {
                if(sum == S)
                    result++;
                return ;
            }
            dfs(sum + nums[cnt], cnt + 1, nums, S);
            dfs(sum - nums[cnt], cnt + 1, nums, S);
        }
    };
    
    C++2
    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int S) {
            int pre[2001],now[2001];
            memset(pre,0,sizeof(pre));
            pre[1000]=1;
            //由于数组下标不可能为负数,这里做了个简单的映射。pre[1000]表示和为0,pre[2000]表示和为1000,pre[0]表示和为-1000。
            for(int i=0;i<nums.size();i++){
                for(int j=0;j<2001;j++)
                    if(pre[j]!=0){
                        now[j+nums[i]]+=pre[j];
                        now[j-nums[i]]+=pre[j];
                    }
                for(int j=0;j<2001;j++){
                    pre[j]=now[j];
                    now[j]=0;
                }
            }
            if(S>1000)
                return 0;
            else
                return pre[S+1000];
        }
    };
    

    相关文章

      网友评论

        本文标题:目标和

        本文链接:https://www.haomeiwen.com/subject/grzsjctx.html