【LeetCode-中等题】15. 三数之和

题目

方法一：哈希表

将四数之和 借助哈希表简化成两数之和

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;  //结果集数量
        Map<Integer,Integer> map = new HashMap<>();//记录前两个数组的和以及出现次数
        for(int i : nums1)
            for(int j : nums2){
             if(!map.containsKey(i+j)) map.put(i+j,1);
             else map.put(i+j,map.get(i+j)+1);
        }

        //遍历后面两个数组取出各自的结果  然后再依次去加上map的key是否等于0，如果是 则将对应的次数加入结果集
        //因为这里已经把四数相加  简化成了两数相加了，并且相加结果要为0    那么他们之间要相加等于0   那么肯定是互为相反数的
         for(int i : nums3)
            for(int j : nums4){
                int temp = (i+j)*-1;//取相反数
                if(map.containsKey(temp)) res+=map.get(temp);//得到相加为0 的数的次数
            }
            return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20