题目地址:
https://leetcode-cn.com/problems/two-sum/
关键点分析:
- 题目比较简单, 暴力破解循环数组, 只有
nums[i] + num[j] == target 就证明找到了相应的值, 将i和j的下标进行返回即可. 复杂度O(n²)
- 遍历一遍将遍历的数据进行缓存, 那么
target - num[i]的值在缓存可以找到, 就证明找到了相应的值. 返回当前i的值以及缓存数据对应的下标即可.
硬循环
public 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};
}
}
}
return new int[] {0, 0};
}
cache版本
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer/*value*/, Integer/*index*/> cache = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (cache.get(target - nums[i]) != null) {
return new int[] {i, cache.get(target - nums[i])};
}
cache.put(nums[i], i);
}
return new int[] {0, 0};
}
}
