LeetCode:1. 两数之和

我不想O(n^2) :(

前置声明

LeetCode所有题目版权均归 LeetCode 和 力扣中国 所有 本文仅提题解与思路，详情请访问官网查看

---

LeetCode:1. 两数之和

O(n)解法:hashmap

下面是我直接用AI写的：
在这个方法中，HashMap扮演了非常重要的角色。它允许我们在O(1)时间复杂度内检查一个数是否已经在之前遍历过的元素中出现过，并且还能够获取到这个数在数组中的索引。这种方法比暴力解法（即使用两层循环遍历数组）要高效得多，因为暴力解法的时间复杂度是O(n^2)，而这种方法的时间复杂度是O(n)。

需要注意的是，HashMap中的键（key）是数组中的元素值，而值（value）是这些元素值在数组中的索引。这种方法利用了HashMap能够快速查找键的特性，从而避免了不必要的重复遍历。

最后，如果遍历完整个数组都没有找到满足条件的两个数，那么方法会抛出一个IllegalArgumentException异常。

import java.util.HashMap;  
import java.util.Map;  
  
class Solution {  
    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);  
        }    
        throw new IllegalArgumentException("No two sum solution");  
    }  
}

O(nlog(n))解法：

我第一眼想到先用对儿值记录值和索引
通过对值进行排序，再用双指针扫两端
这样匹配后可以获得排序之前的索引

不太会java，还是得靠AI找包和各种方法：（

import java.util.Arrays;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建一个可排序的数组来保存值和索引
        int[][] indexedNums = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            indexedNums[i] = new int[]{nums[i], i};
        }
        
        // 按照值对数组进行排序
        Arrays.sort(indexedNums, (a, b) -> Integer.compare(a[0], b[0]));
        
        // 初始化两个指针
        int left = 0, right = nums.length - 1;
        
        // 使用双指针技术寻找匹配对
        while (left < right) {
            int currentSum = indexedNums[left][0] + indexedNums[right][0];
            if (currentSum == target) {
                // 返回原始索引
                return new int[]{indexedNums[left][1], indexedNums[right][1]};
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        // 如果没有找到匹配项，则返回空数组
        return new int[]{};
    }
}