leetcode-两数之和

题目地址:

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};
    }
}