题目

题目解读

1.只存在一个有效答案
2.给一列数字数组nums，和一个目标值target，找到和为target的两数下标

开始解题

一、暴力枚举（双重循环）

        思路：

                尝试所有可能的两个下标组合，看哪一对元素之和等于 target。       

        核心流程：

                1.外层循环固定第一个数的下标 i，从 0 到 n-2。

                2.内层循环固定第二个数的下标 j，从 i+1 到 n-1（因为不能重复使用同一个元素，且 (i,j) 和 (j,i) 是一回事）。

                3.一旦发现 nums[i] + nums[j] == target，直接返回 new int[]{i, j}。

        代码

public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        // 题目保证有解，此行不会执行
        return new int[]{0, 0};
    }

二、基于列表查找（一次循环 + indexOf）

        思路：

                暴力法在内层循环做了太多重复的扫描。我们可以反过来思考：
                对于每个元素 nums[i]，我们需要的另一个数 temp = target - nums[i] 是否在数组中出现过？如果我们把数组转成一个列表，就可以用 indexOf 直接查找 temp 的下标。 

        核心流程：

                1.需要正确地将 int[] 转换成 List<Integer>

                2.查找 temp 时，不仅要判断它是否存在（indexOf 返回 -1 表示不存在），还要保证找到的下标不是 i 本身（避免同一个元素用两次）。

        代码

 public int[] twoSum(int[] nums, int target) {
        // 正确转换：将 int[] 变为 List<Integer>
        List<Integer> numList = Arrays.stream(nums)
                                      .boxed()
                                      .collect(Collectors.toList());
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            int tempIndex = numList.indexOf(temp);
            // indexOf 返回 -1 表示没找到，同时必须不是当前下标
            if (tempIndex != -1 && tempIndex != i) {
                return new int[]{i, tempIndex};
            }
        }
        // 题目保证有解
        return new int[]{0, 0};
    }

三、哈希表（HashMap）

        思路：

                我们需要一种“记住之前看到的元素及其下标”的数据结构，并能快速检查 temp 是否存在 ，所以可以采用HashMap。即每拿到一个新数字，就看过去存的值是否已经包含差值了，没包含就把数字和位置存入。

        核心流程：

                1.创建一个空的 HashMap<Integer, Integer>，键是元素值，值是该元素值对应的下标

                2.从左到右遍历数组。对于当前元素 nums[i]：

                        计算 complement = target - nums[i]。

                        检查 complement 是否已经在 map 的键集合中（说明之前某个下标的元素正好是需要配对的数）。

                                如果在，直接返回 [map.get(complement), i]。

                                如果不在，把 (nums[i], i) 存入 map，继续下一次循环。

        问题点

                为什么不会重复使用同一个元素？
                因为我们总是先查找，后存入。当检查 i 时，map 里只有下标小于 i 的元素，所以找到的 complement 一定不是 nums[i] 自己。

        代码

public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{ map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        // 根据题意，永远会提前返回
        return new int[]{0, 0};
    }

感谢您能够看到这里，一起见证小何同学的算法学习，如果您有不同的见解，希望能得到您的指点和点悟；如果您是和我一样的同学，也希望这篇文章能对您有所帮助。