子数组和问题

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> M;
        for (int i = 0; i < nums.size(); i++) {
            if (M.count(target - nums[i])) {
                return {M[target - nums[i]], i};
            } else {
                M[nums[i]] = i;
            }
        }
        return {0, 0};
    }
};

class Solution {
    vector<vector<int>> ans;
public:
    vector<vector<int>> threeSum(vector<int>& a) {
        sort(begin(a), end(a));
        ans.clear();
        const int n = a.size();
        for (int i = 0; i < n; i++) {
            if (i && a[i-1] == a[i]) continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                if (a[i] + a[j] + a[k] < 0) ++j;
                else if (a[i] + a[j] + a[k] > 0) --k;
                else {
                    ans.push_back({a[i], a[j], a[k]});
                    while (j < k && a[j] == a[j+1]) j++;
                    while (j < k && a[k] == a[k-1]) k--;
                    j++, k--;
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(begin(nums), end(nums));
        const int n = nums.size();
        int ans, diff = INT_MAX;
        auto update = [&](int sum) {
            if (abs(sum - target) < diff) {
                diff = abs(sum - target);
                ans = sum;
            }
        };
        for (int i = 0; i < n - 2; i++) {
            if (i && nums[i] == nums[i-1]) continue;
            int l = i + 1, r = n - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (s == target) return target;
                update(s);
                if (s < target) {
                    while (l < r && nums[l] == nums[l+1]) l++;
                    l++;
                } else {
                    while (l < r && nums[r] == nums[r-1]) r--;
                    r--;
                }
            }
        }
        return ans;
    }
};

class Solution {
    vector<vector<int>> ans;
public:
    vector<vector<int>> fourSum(vector<int>& a, int target) {
        ans.clear();
        sort(a.begin(), a.end());
        const int n = a.size();
        for (int i = 0; i < n; i++) {
            if (i && a[i] == a[i-1]) continue;
            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && a[j] == a[j-1]) continue;
                int l = j + 1, r = n - 1;
                while (l < r) {
                    if (a[i] + a[j] + a[l] + a[r] < target) l++;
                    else if (a[i] + a[j] + a[l] + a[r] > target) r--;
                    else {
                        ans.push_back({a[i], a[j], a[l], a[r]});
                        while (l < r && a[l] == a[l+1]) l++; 
                        while (l < r && a[r] == a[r-1]) r--;
                        l++;
                        r--;
                    }
                } 
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        ans.clear();
        tmp.clear();
        dfs(candidates, target, 0);
        return ans;
    }
    void dfs(vector<int>& cand, int target, int idx) {
        if (idx == cand.size()) return;
        if (target == 0) {
            ans.emplace_back(tmp);
            return;
        }
        dfs(cand, target, idx+1);
        if (target-cand[idx] >= 0) {
            tmp.emplace_back(cand[idx]);
            dfs(cand, target-cand[idx], idx);
            tmp.pop_back();
            // dfs(cand, target-cand[idx], idx+1);
        }
    }
};

class Solution {
   public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<int> candidates;
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        ans.clear();
        tmp.clear();
        sort(candidates.begin(), candidates.end());
        this->candidates = candidates;
        dfs(0, target);
        return ans;
    }
    void dfs(int idx, int target) {
        if (target == 0) {
            ans.emplace_back(tmp);
            return;
        }
        for (int i = idx; i < candidates.size() && (target >= candidates[i]); i++)
        {
            if (i > idx && (candidates[i] == candidates[i-1])) continue;
            tmp.emplace_back(candidates[i]);
            dfs(i+1, target-candidates[i]);
            tmp.pop_back();
        }
    }
};

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ans;
    vector<vector<int>> combinationSum3(int k, int n) {
        for (int i = 0; i < (1<<9); i++) {
            if (check(i, k, n))
                ans.emplace_back(tmp);
        }
        return ans;
    }

    bool check(int cur, int k, int n) {
        tmp.clear();
        for (int i = 0; i < 9; i++) {
            if ((1<<i) & cur) tmp.emplace_back(i+1);
        }
        return (tmp.size() == k && accumulate(tmp.begin(), tmp.end(), 0) == n);
    }
};