1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
S1: brutal force[O($$n^2$$)]
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i = 0; i < nums.size()-1; i++){
for(int j = i+1; j < nums.size(); j++){
if(nums[i] + nums[j] == target){
return vector<int>{i, j};
}
}
return vector<int>{-1, -1};
}
};
};
S2: hashmap time:O(n) space:O(n)
sacrifice space to get time efficiency. Be aware of the corner case that hashmap would return the same index.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++){
map[nums[i]] = i;
}
for(int i = 0; i < nums.size()-1; i++){
int rem = target - nums[i];
if(map.find(rem) != map.end() && map[rem] != i){
return vector<int>{i, map[rem]};
}
}
return vector<int>{-1, -1};
}
};
可以不用提前存进map，边找边存，hashmap搜索范围逐渐变大
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> index;
for (int i = 0; i < nums.size(); ++i) {
if (index.find(target - nums[i]) != index.end()) {
return vector<int>{index[target - nums[i]], i};
} else {
index[nums[i]] = i;
}
}
}
167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
S:two pointer[O(n)]大小pointer两头夹逼
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int smallidx = 0;
int largeidx = numbers.size() - 1;
while (smallidx < largeidx){
if(numbers[smallidx] + numbers[largeidx] == target){
return vector<int>{smallidx+1, largeidx+1};
}
if(numbers[smallidx] + numbers[largeidx] < target){
smallidx++;
}
else{
largeidx--;
}
}
return vector<int>{-1, -1};
}
};
Two Sum II larger
Given an array of integers, find how many pairs in the array such that their sum is bigger than a specific target number. Please return the number of pairs.
Example
Given numbers = [2, 7, 11, 15], target = 24. Return 1. (11 + 15 is the only pair)
S: two pointer
int twoSum2(vector<int> &nums, int target) {
// Write your code here
int size = nums.size();
int left = 0;
int right = size - 1;
int count = 0;
sort(nums.begin(), nums.end());
while (left < right) {
if (nums[left] + nums[right] <= target) {
left++;
} else {
count += right - left;
right--;
}
}
return count;
}
170. Two Sum III - Data structure design
Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
keypoint:
- find the right data structure to store the information.根据操作来选择合适的数据结构，add操作会让vector和array这样的数据结构非常expensive.
- 根据add和find操作的频率来衡量trade-off
S1: hashmap 存储value和count. add操作O(1), find操作O(n).
class TwoSum {
public:
unordered_map<int, int> numbers;
// Add the number to an internal data structure.
void add(int number) {
numbers[number]++;
}
// Find if there exists any pair of numbers which sum is equal to the value.
bool find2(int value) {
for (auto i : numbers) {
if (numbers.find(value - i.first) != numbers.end() &&
(value - i.first != i.first || numbers[value - i.first] > 1)) {
return true;
}
}
}
return false;
}
//A faster version, compare number*2 with value, save one find() in certain case
bool find(int value) {
for(const auto& number :numbers){
if(value == number.first*2 && number.second > 1) return true;
if(value != number.first*2 && numbers.find(value - number.first) != numbers.end())
return true;
}
return false;
}
};
S2: 存储所有可能的sum，add():O($$n^2$$) find:O(1)
class TwoSum {
public:
unordered_set<int> numbers;
unordered_set<int> sum;
// Add the number to an internal data structure.
void add(int number) {
for(const auto& i : numbers){
sum.insert(i + number);
}
numbers.insert(number);
}
bool find(int value) {
if(sum.find(value) != sum.end()) return true;
else return false;
}
};
15. 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
S: sort and two pointer O($$N^2$$)
由于result不能有重复元素，应该考虑先排序,然后skip重复元素。two pointer夹逼
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size() < 3) return result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size()-2; i++){
if(nums[i] > 0) break;
int target = -nums[i];
for(int l = i+1, r = nums.size()-1; l < r;){
if(nums[l] + nums[r] == target){
result.push_back(vector<int>{nums[i], nums[l], nums[r]});
//skip duplicate number
while(l < r && nums[l+1] == nums[l]) l++;
while(l < r && nums[r-1] == nums[r]) r--;
l++;
r--;
}
else if(nums[l] + nums[r] < target){
//skip duplicate number
while(l < r && nums[l+1] == nums[l]) l++;
l++;
}
else{
//skip duplicate number
while(l < r && nums[r-1] == nums[r]) r--;
r--;
}
}
//skip duplicate number
while(i < nums.size()-2 && nums[i+1] == nums[i])i++;
}
return result;
}
};
16. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
S: sort+ two pointer O($$N^2$$)
similar to 3sum, but need to store current closet value and gap.
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int gap = INT_MAX;
int result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size()-2; ++i){
for(int l = i+1, r = nums.size()-1; l < r;){
int sum = nums[i] + nums[l] + nums[r];
int newGap = abs(target -sum);
if(sum == target) return target;
if(newGap < gap){
result = sum;
gap = newGap;
}
if(sum < target) l++;
else r--;
}
}
return result;
}
};
259. 3Sum Smaller
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
S: sort+ two pointer O($$n^2$$)
注意此题和前面几题不同的地方：
- 仅仅需要count, 所以就算进行sort变换index也没有影响。可以用two pointer把二维问题转化为一维解决。
- 需要比较的是小于。只要nums[l]+num[r]<target, 那对于任意l<i<r都有nums[l]+nums[i]<target。
note：根据需要的result来变通解法， 并利用条件及时结束循环.
因为是sorted array,只要nums[i]+nums[i+1]+nums[i+2]>=target就没必要继续loop。
class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
if(nums.size() < 3) return 0;
int result = 0;
sort(nums.begin(), nums.end());
//及时结束循环
for(int i = 0; i < nums.size() - 2 && nums[i] + nums[i+1]*2 < target; ++i){
for(int l = i+1, r = nums.size()-1; l < r;){
int sum = nums[i] + nums[l] + nums[r];
if(sum < target){
result += r - l;
l++;
}
else r--;
}
}
return result;
}
};
Triangle Count
Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?
Example
Given array S = [3,4,6,7], return 3. They are:
[3,4,6]
[3,6,7]
[4,6,7]
Given array S = [4,4,4,4], return 4. They are:
[4(1),4(2),4(3)]
[4(1),4(2),4(4)]
[4(1),4(3),4(4)]
[4(2),4(3),4(4)]
S: two pointer
由i,j,k可组成三角形的条件是任意两边大于第三边：
1. i+j>k 2. j+k>i 3. i+k>j
对于i<j<k第2，3条是一定满足的，只要找到满足1的三边即可，就是two sum II larger的问题。
int triangleCount(vector<int> &S) {
// write your code here
int size = S.size();
int count = 0;
sort(S.begin(), S.end());
for (int k = 2; k < size; ++k) {
int left = 0;
int right = k - 1;
while (left < right) {
if (S[left] + S[right] > S[k]) {
count += right - left;
right--;
} else {
left++;
}
}
}
return count;
}
18. 4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
S: sort+two pointer O(N^3)
和2sum,3sum思路一样只是多一层loop
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
if(nums.size() < 4) return result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size()-3; i++){
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;
if(i > 0 && nums[i] == nums[i-1]) continue;
for(int j = i+1; j < nums.size()-2; j++){
if(j > i+1 && nums[j] == nums[j-1]) continue;
for(int l = j+1, r = nums.size()-1; l<r;){
int sum = nums[i] + nums[j] + nums[l] + nums[r];
if(sum == target){
result.push_back(vector<int>{nums[i], nums[j], nums[l], nums[r]});
while(nums[l] == nums[l+1] && l<r) l++;
while(nums[r] == nums[r-1] && l<r) r--;
l++;
r--;
}
else if(sum < target){
while(nums[l] == nums[l+1] && l<r) l++;
l++;
}
else{
while(nums[r] == nums[r-1] && l<r) r--;
r--;
}
}
}
}
return result;
}
};