給定一個整數(shù)數(shù)組 nums?和一個目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那?兩個?整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解題思路
中心思路是遍歷數(shù)組判斷“目標(biāo)值 - 遍歷元素”所得值在不在數(shù)組中
代碼
class Solution {
? ? public int[] twoSum(int[] nums, int target) {
? ? ? List<Integer> result = new ArrayList<>();
? ? ? ? // 將數(shù)組元素與下標(biāo)封裝map，方便遍歷判斷
? ? ? ? Map<Integer, Integer> map = new HashMap<>();
? ? ? ? for (int i = 0; i < nums.length; i++) {
? ? ? ? ? ? map.put(i, nums[i]);
? ? ? ? }
? ? ? ? // 目標(biāo)元素 - 遍歷元素結(jié)果
? ? ? ? int tmp;
? ? ? ? // 針對目標(biāo)值是元素2倍情況，控制不進(jìn)行重復(fù)判斷
? ? ? ? boolean check = true;
? ? ? ? // 元素下標(biāo)集合
? ? ? ? Set<Integer> set = map.keySet();
? ? ? ? // 遍歷下標(biāo)
? ? ? ? for (Integer k : set) {
? ? ? ? ? ? Integer v = map.get(k);
? ? ? ? ? ? // 目標(biāo)值 - 遍歷元素
? ? ? ? ? ? tmp = target - v;
? ? ? ? ? ? // 判斷所得值是否在數(shù)組中
? ? ? ? ? ? if (map.containsValue(tmp)) {
? ? ? ? ? ? ? ? // 1.存在2倍關(guān)系
? ? ? ? ? ? ? ? if (v == target / 2 && check && v != 0) {
? ? ? ? ? ? ? ? ? ? // 根據(jù)value查詢對應(yīng)所有key
? ? ? ? ? ? ? ? ? ? int[] arr = getMapKeyByValue(map, tmp);
? ? ? ? ? ? ? ? ? ? if (arr.length > 1) {
? ? ? ? ? ? ? ? ? ? ? ? result.add(arr[0]);
? ? ? ? ? ? ? ? ? ? ? ? result.add(arr[1]);
? ? ? ? ? ? ? ? ? ? ? ? check = false;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? // 2.不存在2倍關(guān)系
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? result.add(k);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 如果存在2倍關(guān)系，但是數(shù)組中只有一個元素，比如6 和 3，數(shù)組中只有3，那么不作為結(jié)果返回
? ? ? ? if (result.size() < 2) {
? ? ? ? ? ? return new int[]{};
? ? ? ? }
? ? ? ? return result.stream().distinct().mapToInt(Integer::valueOf).toArray();
? ? }
? ? private static int[] getMapKeyByValue(Map<Integer, Integer> map, int target) {
? ? ? ? List<Integer> list = new ArrayList<>();
? ? ? ? map.forEach((k, v) -> {
? ? ? ? ? ? if (v.equals(target)) {
? ? ? ? ? ? ? ? list.add(k);
? ? ? ? ? ? }
? ? ? ? });
? ? ? ? return list.stream().mapToInt(Integer::valueOf).toArray();
? ? }
}
