1. 两数之和

发表评论
542 views

 ›
1. 两数之和

官方链接

https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

判断一个数在集合内是否存在，要用到数据结构 Set 或者 哈希表 Python 2.3. 以上版本可用 enumerate ，2.6 添加 start 参数 :

# enumerate(sequence, [start=0])
seq = ['one', 'two', 'three']
for i, element in enumerate(seq):
    print(i, element)

解法一 暴力求解

O(N^2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j]; 
                if (sum == target) return new int[]{i, j};
            }
        }
        return new int[]{};
    }
}

解法二 HashMap

O(N)

HashMap: x + y = 9 => y = 9 - x

for: x:0 -> length O(N)
HashMap: 9-x -> O(1)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> m = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
           m.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int another = target - nums[i];
            if (m.containsKey(another) && m.get(another) != i) return new int[]{i, m.get(another)};
        }

        return new int[]{};
    }
}

用 Set 的话，没办法知道值的下标，多了一次循环查找

class Solution {
    public int[] twoSum(int[] nums, int target) {

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if (set.contains(x)) {
                for (int j = 0; j < i; j++) {
                    if (nums[j] == x) return new int[]{j, i};
                }
            } else set.add(nums[i]);
        }
        return new int[]{};
    }
}

解法三 解法二的基础上减少一次循环

class Solution {
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> m = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if (m.containsKey(x)) {
                return new int[]{i, m.get(x)};
            } else m.put(nums[i], i);
        }
        return new int[]{};
    }
}