🕒 阅读时间：2 分钟 📝 字数：445 👀 阅读量： Loading...
我不想O(n^2) :(
LeetCode所有题目版权均归 LeetCode 和 力扣中国 所有
本文仅提题解与思路，详情请访问官网查看
下面是我直接用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");
}
}
我第一眼想到先用对儿值记录值和索引 通过对值进行排序，再用双指针扫两端 这样匹配后可以获得排序之前的索引
不太会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[]{};
}
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。