首页 > 代码库 > Sum 总结

Sum 总结

sum无非两种情况,用hashtable 或者用 2 pointer。 Hashtable的时候多不需要考虑重复问题,但是2 pointer往往要考虑重复问题。解决重复问题的方法为初始时判断,如果不是i=0或者nums[i] != nums[i-1],那就跳过。这样保证第一个值不可能是一样的。同理,在loop里面,当target等于和的时候,左右pointer也要先查重。

 

  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].

 

Hashtable 存nums[i], I;

 

  1. 3Sum

Given an array S of n integers, are there elements abc 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]
]

 

几个关键点:

可能会有重复,需要logic来去掉重复。

另一个关键点是本身不sort,需要sort。

Conditions: sort完最左边大于0或者最右边小于0, 直接return。

2 pointer的时候注意不是一有结果就break,也可能left往右right往左还有符合的结果。

while(left<right && nums[left+1] ==nums[left])    left++;

 while(left<right && nums[right-1] ==nums[right])  right--;

 

  1. 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]

Follow up:
Could you solve it in O(n2) runtime?

 

思路跟3 sum是一样的,只是加的时候, res + = right-left, 因为只要三个和小于target, 那right左边到left的所以都是符合的。

 

  1. 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).

这个题也是一样的,只是需要每次判断哪个更小,如果更小,更新res为更小的那个。

 

  1. 4Sum

跟3 sum完全一样,多加了一层。需要注意的还是不能重复。

Sum 总结