2 Sum Variants

Two Sum

For the problem that need to return the two numbers, we can sort the array and use two pointers method.

1
2
3
4
5
6
7
8
9
vector<int> twoSum(vector<int>& numbers, int target) {
sort(numbers.begin(), numbers.end());
int n = numbers.size();
int left = 0, right = n-1;
while (numbers[left]+numbers[right] != target)
if (numbers[left]+numbers[right] < target) left++;
else right--;
return {numbers[left+1], numbers[right+1]};
}

For the problem that need to return the indices of the two numbers, we need to use a hash map to save visted numbers and serach in every iterations.

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
unordered_map<int, int> M;
for (int i = 0; i < nums.size(); i++)
{
int numberToFind = target - nums[i];
if (M.find(numberToFind) != M.end()) {
return {M[numberToFind], i};
}

M[nums[i]] = i;
}
}

Three Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (int i = 0; i < int(nums.size()) - 2; i++)
{
if (i > 0 && nums[i] == nums[i-1]) continue;
int target = 0 - nums[i];
int left = i + 1, right = nums.size() - 1;
while (left < right)
{
if (nums[left] + nums[right] == target) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}
else if (nums[left] + nums[right] < target) left++;
else right--;
}
}

return result;
}

Three Sum Closest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int error = INT_MAX, sum = 0;
for (int i = 0; i < n - 2; i++)
{
if (i != 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = n - 1;
int target2 = target - nums[i];

while (left < right)
{
int sum2 = nums[left] + nums[right];
if (abs(target2 - sum2) < error) {
error = abs(target2 - sum2);
sum = nums[i] + sum2;
if (sum == target) return sum;
}
if (sum2 + nums[i] < target) left++;
else right--;
}
}

return sum;
}

Four Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> total;
int n = nums.size();
if(n<4) return total;
sort(nums.begin(),nums.end());
for(int i=0;i<n-3;i++)
{
if(i>0&&nums[i]==nums[i-1]) continue;
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
for(int j=i+1;j<n-2;j++)
{
if(j>i+1&&nums[j]==nums[j-1]) continue;
if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
int left=j+1,right=n-1;
while(left<right){
int sum=nums[left]+nums[right]+nums[i]+nums[j];
if(sum<target) left++;
else if(sum>target) right--;
else{
total.push_back({nums[i],nums[j],nums[left],nums[right]});
do{left++;}while(nums[left]==nums[left-1]&&left<right);
do{right--;}while(nums[right]==nums[right+1]&&left<right);
}
}
}
}
return total;
}

Number of Subarraies Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int subarraySum(vector<int>& nums, int k) {
int count = 0;
int sum = 0;
map<int, int> m;
m[0] = 1;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i];
count += m[sum-k];
m[sum]++;
}

return count;
}

Maximum Size Subarray Sum Equals K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<int, int> sums; // <sum, end_index>
int cur_sum = 0;
int max_len = 0;
for (int i = 0; i < nums.size(); i++) {
cur_sum += nums[i];
if (cur_sum == k) {
max_len = i + 1;
} else if (sums.find(cur_sum - k) != sums.end()) {
max_len = max(max_len, i - sums[cur_sum - k]);
}
if (sums.find(cur_sum) == sums.end()) {
sums[cur_sum] = i;
}
}
return max_len;
}

Minimum Size Subarray Sum

1
2
3
4
5
6
7
8
9
10
11
12
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size(), start = 0, sum = 0, minlen = INT_MAX;
for (int i = 0; i < n; i++) {
sum += nums[i];
while (sum >= s) {
minlen = min(minlen, i - start + 1);
sum -= nums[start];
start++;
}
}
return minlen == INT_MAX ? 0 : minlen;
}

Contiguous Array

Variant of ‘Maximum Size Subarray Sum Equals K’ problem, where zeros are -1, ones are 1 and K = 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
int findMaxLength(vector<int>& nums) {
int size = nums.size(), ballance = size, max_len = 0;
int ballances[size * 2 + 1] = {};
for (auto i = 0; i < size; ++i) {
ballance += nums[i] == 0 ? -1 : 1;
if (ballance == size) max_len = i + 1;
else {
if (ballances[ballance] != 0) max_len = max(max_len, i - ballances[ballance] + 1);
else ballances[ballance] = i + 1;
}
}
return max_len;
}