523. Continuous Subarray Sum

Given a list ofnon-negativenumbers and a targetintegerk, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple ofk, that is, sums up to n*k where n is also aninteger.

Example 1:

Input:
 [23, 2, 4, 6, 7],  k=6

Output:
 True

Explanation:
 Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input:
 [23, 2, 6, 4, 7],  k=6

Output:
 True

Explanation:
 Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

S: preSum + hashmap + mod O(n)

对preSum数组，preSum - x = nk => x = preSum - nk 等式两边对k取模 x%k = (preSum - nk)%k => x%k = preSum%k 只需存储preSum对k的模结果即可

    bool checkSubarraySum(vector<int>& nums, int k) {
        if (k < 0) {
            k = -k;
        }
        int preSum = 0;
        unordered_map<int, int> map;
        map[0] = -1;
        for (int i = 0; i < nums.size(); ++i) {
            preSum += nums[i];
            if (k > 0) {
                preSum %= k;
            }
            if (map.find(preSum) != map.end()) {
                if (i - map[preSum] > 1) {
                    return true;
                }
            } else {
                map[preSum] = i;
            }
        }
        return false;
    }

525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1] Output: 2

Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0] Output: 2

Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

S： presum + hashmap O(n)

把0转化为-1,问题转化为求和为0的最长子序列，用presum和hash map即可求解

    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n == 0 || n == 1) {
            return 0;
        }
        unordered_map<int, int> map;
        int preSum = nums[0] == 0? -1 : 1;
        map[0] = -1;
        map[preSum] = 0;
        int maxLen = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 1) {
                preSum++;
            } else {
                preSum--;
            }
            if (map.find(preSum) != map.end()) {
                maxLen = max(maxLen, i - map[preSum]);
            } else {
                map[preSum] = i;
            }
        }
        return maxLen;
    }

Continuous Subarray Sum II

Given an circular integer array (the next element of the last element is the first element), find a continuous subarray in it, where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number.

If duplicate answers exist, return any of them.

Example

Give[3, 1, -100, -3, 4], return[4,1].

S1: 复制到2倍长度

//注意：code没有通过所有测试
       vector<int> continuousSubarraySumII(vector<int>& A) {
        int n = A.size();
        vector<int> result(2, 0);
        if (n < 1) {
            return result;
        }
        int start = 0;
        int sum = 0;
        int maxSum = INT_MIN;
        for (int i = 0; i < 2 * n; ++i) {
            if (i - start >= n) {
                sum -= A[start%n];
                start++;
            }
            if (sum < 0) {
                sum = 0;
                start = i;
            }
            sum += A[i%n];
            if (sum >= maxSum) {
                maxSum = sum;
                result[0] = start % n;
                result[1] = i % n;
            }
        }
        return result;
    }

S2： 对首尾相连的情况反向求解，即求中间段的最小值

Subarray Sum Closest

Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Example

Given[-3, 1, 1, -3, 5], return[0, 2],[1, 3],[1, 1],[2, 2]or[0, 4].

S：将presum排序

注意custom的comparator不能是member function, 若是要用static

struct myNode {
    int sum;
    int idx;
    myNode (int a, int b): sum(a), idx(b) {};
};
bool cmp(myNode* a, myNode* b) {
    return a->sum <= b->sum;
}
class Solution {
public:
    vector<int> subarraySumClosest(vector<int> nums) {
        vector<int> result(2);
        int minGap = INT_MAX;
        int n = nums.size();
        vector<myNode*> preSum(n + 1);
        myNode dummy(0, -1);
        preSum[0] = &dummy;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            myNode* node = new myNode(sum, i);
            preSum[i + 1] = node;
        }
        sort(preSum.begin(), preSum.end(), cmp);
        for (int i = 0; i < n; ++i) {
            int gap = preSum[i + 1]->sum - preSum[i]->sum;
            if (gap < minGap) {
                minGap = gap;
                result[0] = min(preSum[i]->idx, preSum[i + 1]->idx) + 1;
                result[1] = max(preSum[i]->idx, preSum[i + 1]->idx);
            }
        }
        return result;
    }
};