和为k的子数组 LeetCode 560

和为k的不重复子数组个数(包含不连续)：

和为k的子数组 LeetCode 560

Example 1:
Input:nums=[1,1,1],k=2  Output:2
 
Example 2:
Input:nums=[1,2,3],k=3 Output:2
 
Example 3:
Input:nums=[1,-1,0],k=0 Output:3
 

c++代码：这个是说相邻两个数求和为3的解

如果数字为[1,3,2]，结果就只有1个了。

#include <iostream>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans=0,j,temp;
        for(int i=0;i<nums.size();i++){
            temp=0;
            j=i;
            while(j<nums.size()){
                temp+=nums[j];
                if(temp==k){//不能跳出循环,负数可能反转为k,需要遍历完
                    ans++;
                }
                j++;
            }
        }
        return ans;
    }
 
     int subarraySumOne(vector<int>& nums, int k){
         unordered_map<int,int> dp;
         dp[0]=1;//nums存在元素刚好等于k的情况
         int ans=0,pre=0;
         for(auto& n:nums){
             pre+=n;
             //pre[i]-pre[j-1]=k
             //若dp中存在,key为[当前前缀和-k],说明这个之前出现的前缀和,满足
             //[当前前缀和-该前缀和==k],它出现的次数,累加给count.
             if(dp.count(pre-k)){
                 ans+=dp[pre-k];
             }
             dp[pre]++;//若没有存过,则存入,初始值为1.若存在,则value+1
         }
         return ans;
     }
};
 
int main(int argc,char* argv[]){
    vector<int> nums={1,-1,0,1,-1,0};//{1,2,3,1,-1,0};
    int k=0;
    cout<<Solution().subarraySum(nums,k)<<endl;
    return 0;
}

原文链接：https://blog.csdn.net/Jiangtagong/article/details/113837682

和为k的不重复子数组个数(包含不连续)：

调用，返回和为k的子数组的个数，元素不能重复，不连续也可以。

int data[5] = { 1,2,4,2,5 };

	//int[] data = { 1,2,3,2,4,5 };
	int target = 5;
	int data_len = 5;

	int res;
	res=child_sum(data, target, data_len);

int child_sum(int *data, int target, int data_len) {

	int TotalSum = 0;

	std::set<int> set_used = { };

	std::vector<int> cur_used;

	int count = 0;
	for (int right = data_len - 1; right >= 0; right--) {
		for (int left = right; left >= 0; left--) {
			if (!set_used.count(data[left])) {
				if (TotalSum + data[left] <= target) {
					TotalSum = TotalSum + data[left];
					cur_used.push_back(data[left]);
					if (TotalSum == target) {
						for (vector<int>::iterator it = cur_used.begin(); it != cur_used.end(); it++) {
							std::cout << " " << *it << " ";
							set_used.insert(*it);
						}
						std::cout << std::endl;
						set_used.insert(data[left]);
						count++;
						TotalSum = 0;
						cur_used.clear();
					}
				}

			}
		}
		cur_used.clear();
		TotalSum = 0;
	}
	return count;
}