两数之和

文章：5. 两数之和

题目：1. 两数之和

【思路】

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[]res = new int[2];
        for(int i = 0;i< nums.length;i++){
            int t = target-nums[i];
            if(map.containsKey(t)){
                res[1] = i;
                res[0] = map.get(t);
                break;
            }
            map.put(nums[i],i);
        }
        return res;
    }
}
  • Go
1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
    m := make(map[int]int,0)
    for i:=0;i<len(nums);i++{
        t := target-nums[i]
        if _,ok:=m[t];ok{
            return []int{m[t],i}
        }
        m[nums[i]] = i//把当前数值存进map
    }
    return []int{}
}

四数之和II

文章：6. 四数相加II

题目：454. 四数相加 II

【思路】

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int res = 0;
        for(int i :nums1){
            for(int j : nums2){
                int sum = i+j;
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }
        for(int i : nums3){
            for(int j:nums4){
                res+=map.getOrDefault(0-i-j,0);
            }
        }
        return res;
    }
}
  • Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    res := 0
    m := make(map[int]int)
    for _,i := range nums1{
        for _,j := range nums2{
            m[i+j]++
        }
    }
    for _,i:= range nums3{
        for _,j := range nums4{
            res += m[0-i-j]
        }
    }
    return res
}

三数之和

文章：8. 三数之和

题目：15. 三数之和

【思路】

结合双指针

  • Java
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
31
32
33
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //双指针法
        List<List<Integer>> res = new ArrayList<>();
      
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-2 ;i++){
            if(i > 0&& nums[i]== nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while(right > left){
                int temp = nums[i] + nums[left]+nums[right];
                if(temp > 0){
                    right--;
                }else if(temp <0){
                    left++;
                }else{
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(right > left && nums[right] == nums[right-1]){right--;}
                    while(right > left && nums[left] == nums[left+1])left++;
                    right--;
                    left++;
                }
            }

        }
        return res;

    }
}

  • Go

排序： sort.Ints(nums)

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
31
32
33
34
35
func threeSum(nums []int) [][]int {
    //Go的排序
    sort.Ints(nums)
    res := [][]int{}
    for i := 0 ; i <len(nums)-2;i++{
        if nums[i] > 0 {
            return res
        }
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }
        left := i+1
        right := len(nums)-1
        for left < right{
            sum := nums[i] + nums[left]+nums[right]
            if sum == 0{
                n2,n3 := nums[left],nums[right]
                res = append(res,[]int{nums[i],n2,n3})
                for right > left && nums[right] == nums[right-1]{
                    right--
                }
                for right > left && nums[left] == nums[left+1]{
                    left++
                }
                left++
                right--
            }else if sum < 0{
                left++
            }else{
                right--
            }
        }
    }
    return res
}

四数之和

文章：9. 四数之和

题目：

【思路】

在三数之和的基础上套多一层for循环

  • Java
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
31
32
33
34
35
36
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>>res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0 ; i < nums.length;i++){
            if(nums[i] >0 && nums[i]>target)return res;//剪枝
            if( i > 0 && nums[i] == nums[i-1])continue;
            for(int j = i+1 ; j < nums.length ;j++){
                if(j > i + 1 && nums[j] == nums[j-1])continue;
                int left = j+1;
                int right = nums.length-1;
                while(right > left){
                    int n2 = nums[left];
                    int n3 = nums[right];
                    long sum = (long)(nums[i]+nums[j]+n2+n3);
                    if(sum >target)right--;
                    else if(sum < target) left++;
                    else{
                        res.add(Arrays.asList(nums[i],nums[j],n2,n3));
                        while(right > left && nums[right] == nums[right-1]){
                            right--;
                        }
                        while(right > left && nums[left] == nums[left+1]){
                            left++;
                        }
                        left++;
                        right--;
                    }    
                }
                
            }
           
        }
         return res;
    }
}
  • Go
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
31
32
33
34
35
36
37
38
39
40
41
func fourSum(nums []int, target int) [][]int {
    if len(nums) < 4 {
        return nil
    }
    sort.Ints(nums)
    var res [][]int
    for i := 0;i < len(nums)-3;i++{
        n1 := nums[i]
        if i>0 && nums[i] == nums[i-1]{
            continue
        }
        for j:=i+1;j<len(nums)-2;j++{
            n2 := nums[j]
            if j > i+1 && nums[j] == nums[j-1]{
                continue
            }
            left ,right := j+1,len(nums)-1
            for right > left{
                n3 := nums[left]
                n4 := nums[right]
                sum := n1+n2+n3+n4
                if(sum > target){
                    right--
                }else if(sum < target){
                    left++
                }else{
                    res = append(res,[]int{n1,n2,n3,n4})
                    for right > left && n3 == nums[left+1]{
                        left++
                    }
                    for right > left && n4 == nums[right-1]{
                        right--
                    }
                    left++
                    right--
                }
            }
        }
    }
    return res
}

【总结】

复习了哈希表以及双指针的用法