Java实现LeetCode（1.两数之和）

一、题目描述

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

你可以假设每个输入只对应一种答案，并且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

二、思路分析

1.暴力法

最容易想到的思路是循环每个数，并查找是否存在与其配对的目标元素。我们可以通过嵌套循环的方式来简单实现：

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[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)

2.哈希表法

通过使用哈希表，我们可以将寻找目标元素的时间从 O(N) 降低到 O(1)。使用哈希表的时候，需要遍历一次数组并将每个元素及其下标添加到哈希表中，然后遍历一次数组并查找其目标元素是否存在于哈希表中。

public static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

三、完整代码

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

public class Solution {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        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(result[0] + " " + result[1]);
        // 输出：0 1
    }
}

四、两条示例说明

1.输入数组无解

若给定数组为 [1, 2, 3, 4]，目标元素为 9，无解。

public static void main(String[] args) {
    int[] nums = {1, 2, 3, 4};
    int target = 9;
    try {
        int[] result = twoSum(nums, target);
        System.out.println(result[0] + " " + result[1]);
    } catch (Exception e) {
        System.out.println(e.getMessage());
        // 输出：No two sum solution
    }
}

2.数组中存在相同元素

若给定数组为 [2, 2, 3, 4], 目标元素为 4，返回 [0, 1]。

public static void main(String[] args) {
    int[] nums = {2, 2, 3, 4};
    int target = 4;
    int[] result = twoSum(nums, target);
    System.out.println(result[0] + " " + result[1]);
    // 输出：0 1
}