11. 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数

要在一个整数数组中找出和为目标值的两个数，可以使用以下几种方法。最常见的解法包括暴力枚举、哈希表存储法等。下面分别介绍这些方法，并提供 Java 代码示例。

一、暴力枚举法

1. 思路

暴力枚举法的思路是使用两个嵌套的循环，枚举数组中的每一个可能的数对，检查它们的和是否等于目标值。如果找到和为目标值的两个数，则返回它们的索引。

2. 代码实现

public class TwoSumBruteForce {
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j}; // 找到符合条件的两个数的索引
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Indexes: " + result[0] + ", " + result[1]);
    }
}

3. 时间复杂度

• 时间复杂度：O(n^2)，其中 n 是数组的长度。每对数字都要进行比较，因此时间复杂度较高。
• 空间复杂度：O(1)，仅使用了常数级别的额外空间。

二、哈希表存储法

1. 思路

使用哈希表可以将时间复杂度降为 O(n)。具体步骤是遍历数组，将每个元素和其索引存入哈希表，并检查目标值减去当前元素的差值是否已经在哈希表中。如果存在，则说明找到了两个数，它们的和等于目标值。

2. 代码实现

import java.util.HashMap;
import java.util.Map;

public class TwoSumHashMap {
    public static 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); // 将当前数字和它的索引放入哈希表
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Indexes: " + result[0] + ", " + result[1]);
    }
}

3. 时间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度。每个元素只需被访问一次。
• 空间复杂度：O(n)，哈希表存储了数组中的每个元素。

三、双指针法（适用于有序数组）

1. 思路

如果数组是有序的，可以使用双指针法。将两个指针分别放在数组的头部和尾部，逐渐向中间移动，直到找到和为目标值的两个数。

2. 代码实现

import java.util.Arrays;

public class TwoSumTwoPointers {
    public static int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[]{left, right}; // 找到符合条件的两个数的索引
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Indexes: " + result[0] + ", " + result[1]);
    }
}

3. 时间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

四、总结

• 暴力枚举法：简单直观，但时间复杂度高，适用于小规模数据。
• 哈希表存储法：效率高，适用于任意顺序的数组，时间复杂度为 O(n)。
• 双指针法：适用于已排序的数组，时间复杂度为 O(n)，且空间复杂度为 O(1)。

在实际开发中，哈希表存储法通常是最常用的解决方案，因其时间复杂度较低且适用于无序数组。双指针法则在处理有序数组时更为高效。

阅读全文