LeetCode:1. 两数之和
发布时间：
更新时间：
我不想O(n^2) :(
前置声明
LeetCode所有题目版权均归 LeetCode 和 力扣中国 所有本文仅提题解与思路，详情请访问官网查看
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[]{}; }}
留言评论