计算两数之和

第一次做leetcode题目，先拿一个最简单的练下手。

题目

题目地址：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]

答案

方法一

暴力破解法

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
      for (int i = 0; i < nums.length; i++) {
          for (int j = 0; j < nums.length; j++) {
              if (i == j) {
                  continue;
              }
              if (nums[i] + nums[j] == target) {
                  return new int[] {i, j};
              }
          }
      }
      return null;
  }

运行消耗：

  • 执行时间：102 ms
  • 内存消耗：39.7 MB

时间复杂度：O(n^2)
对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)。

空间复杂度：O(1)。

方法二

利用Map数据结构，每次循环时使用目标值减去当前值，如果结果在map中存在，直接返回，不存在，并将当前值存储在map中，方便下次循环判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int res = target - nums[i];
            if (map.containsKey(res)) {
                return new int[] {map.get(res), i};
            }
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }
        }
        return null;
    }

运行消耗：

  • 4 ms
  • 内存消耗：40.1 MB

时间复杂度：由于只有一个for循环，所以时间复杂度为O(1)
空间复杂度：只需要将数组中的存储到map中，所有空间复杂度为O(1)