关于算法:算法-哈希表-两数之和-与-四数之和

第一题 两数之和

力扣 第一题：两数之和

 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。你能够按任意程序返回答案。示例 1：输出：nums = [2,7,11,15], target = 9
输入：[0,1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。示例 2：输出：nums = [3,2,4], target = 6
输入：[1,2]
示例 3：输出：nums = [3,3], target = 6
输入：[0,1]

起源：力扣（LeetCode）链接：https://leetcode.cn/problems/two-sum
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

办法 1：循环遍历两次，工夫复杂度 O(n*n)

办法 2：哈希表映射，遍历一次，工夫复杂度 O(n)

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){if(map.containsKey(target-nums[i])){return new int[]{i, map.get(target-nums[i])};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

第二题：四数相加 II

力扣 454 题，四数相加

 给你四个整数数组 nums1、nums2、nums3 和 nums4，数组长度都是 n，请你计算有多少个元组 (i, j, k, l) 能满足：0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
 

示例 1：输出：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输入：2
解释：两个元组如下：1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：输出：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输入：1

起源：力扣（LeetCode）链接：https://leetcode.cn/problems/4sum-ii
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解答：能够应用第一题思路，讲 4 组数组分成 2 组

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        int n = nums1.length;

        Map<Integer, Integer> map = new HashMap<>();

        for(int a =  0; a < n ; a++) {for(int b  = 0 ;  b < n; b++){int sum = nums1[a] + nums2[b];
                if(map.get(sum) == null) {map.put(sum, 1);
                }else {map.put(sum, map.get(sum)+1);
                }
            }
        }

        for(int a = 0; a < n; a++) {for(int b = 0; b < n; b++) {int sum = nums3[a] + nums4[b];
                if(map.get(0-sum) != null){count+= map.get(0-sum);
                }
            }
        }

        return count;
    }
}