LeetCode | 1 Two Sum

分析

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

寻找两个不同元素相加等于目标值并返回其索引。

梦开始的地方也是梦夭折的地方！

这个题目，刻意摘录下原题英文描述，因为我觉得英文描述的更加准确。indices of the two numbers即返回的是目标数据的索引下标，not use the same element twice表明，一个索引只能被用一次，即便是比如目标值为10，而索引1对应的元素值为5，也不能自己跟自己相加，得出错误结果[1,1]。

依据题目的意思，原始的数组，索引跟数据是一对一绑定，倘若我们自行在这个数组之上进行去重或者排序都会破坏这个数组的原有结构，与我们的最终结果背道而驰。在这种情况下，我就需要先将数据元素值和索引下标进行包装，形成一个独立的数据。因为数据本身无法独立存在，需要能够装它的容器，很容易想到键值对的结构Map。

接着问题就来了，键值对的键在此刻是选择原始的索引下标呢，还是数据元素值呢？倘若我使用的是索引下标，那么这样的Map结构就退化到了数组结构，也就是自己的这种包装毫无意义。用数据元素值作为索引，类似于一种依赖倒置，嗯，我需要的也是通过元素寻找索引。

可还没有解决问题，又该如何去寻找这两个数呢？嗯，不妨换个思路，target = wrappedA + wrappedB 转换为 wrappedB = target - wrappedA,有什么区别吗？在已知target和遍历过程中的获得的确定值wrappedA,去寻找未知的wrappedB,把原本两个自由量降低为1个自由量，寻找唯一元素，边存数据，边找数据，Hash结构的主场了。

从LeetCode242 Valid-Anagram这道题的解法，那时候我在思考，Hash结构这个容器，一个数组把数据存放进去，另一个数组相当于取出与条件相匹配的数据,在Valid-Anagram中是寻找字母个数相同的所有数据，在这道题取出与放入的数据之和为目标值的数据。

总结

• 原始数据结构需要保护，使用键值对生成对应的包装数据
• 利用哈希表来配对：对于每个元素nums[i],计算target-nums[i]

主类

package com.github.dolphinmind.hash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author dolphinmind
 * @ClassName TwoSum
 * @description
 * @date 2024/8/9
 */

public class TwoSum {

    /**
     * 获取单个结果即返回
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumGetOneResult(int[] nums, int target) {
        if (nums == null || nums.length < 2 ) {
            return null;
        }

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

        for (int i = 0; i < nums.length; i++) {
            int difference = target - nums[i];
            if (map.containsKey(difference)) {
                return new int[]{map.get(difference),i};
            }

            map.put(nums[i],i);
        }
        return new int[0];
    }

    /**
     * 获取所有结果
     */

    public List<List<Integer>> twoSumGetAllResult(int[] nums, int target) {
        if (nums == null | nums.length < 2) {
            return null;
        }

        //值：索引列表
        Map<Integer, List<Integer>> map = new HashMap();
        // 索引对结果集合
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if (map.containsKey(complement)) {
                for (int index : map.get(complement)) {
                    List<Integer> pair = new ArrayList<>();
                    pair.add(index);
                    pair.add(i);
                    res.add(pair);
                }
            }

            map.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        return res;

    }
}

测试类

package com.github.dolphinmind.hashcode;

import com.github.dolphinmind.hash.TwoSum;
import org.junit.Test;

import java.util.List;

/**
 * @author dolphinmind
 * @ClassName TwoSumTest
 * @description
 * @date 2024/8/9
 */

public class TwoSumTest {

    @Test
    public void test_towSumGetOneResult() {
        int[] nums = {1,3,5,7,8,9};
        int target = 10;

        TwoSum twoSum = new TwoSum();
        int[] res = twoSum.twoSumGetOneResult(nums, target);
        System.out.println("获取单个索引对结果："+res[0] + " " + res[1]);

        List<Integer> integers = twoSum.twoSumGetAllResult(nums, target).get(0);
        System.out.println("获取所有索引对结果："+integers.get(0) + " " + integers.get(1));
    }

    @Test
    public void test_towSumGetAllResult() {
        int[] nums = {1,1,1,3,5,7,8,9,7,8,9};
        int target = 10;

        TwoSum twoSum = new TwoSum();
        List<List<Integer>> lists = twoSum.twoSumGetAllResult(nums, target);
        for (List<Integer> list : lists) {
            System.out.println(list.get(0) + " " + list.get(1));
        }

        System.out.println(lists.get(0));
    }
}