跳转至

0405_两数之和

Algorithm：两数之和

题目描述

leecode01 两数之和

给定一个整数数组 nums 和一个目标值target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

b站讲解视频

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

solution 1

定义两个下标 i，j

当i=0时，j循环遍历剩下的数，判断存在i + j = target的，存在就返回下标i，j；不存在就i=1继续循环遍历

时间复杂度比较高

solution 2

使用查找表来解决

定义一个map集合，用来存储数据，数据的下标

  1. 循环遍历数组，计算出target - nums[i]的值是否在map里存在；
  2. 若存在，就返回map里这个差值的value和 i；若不存在，就将num[i]作为key，i作为value存入map中，继续循环

java代码

solution 1

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

solution 2

 public int[] twoSum(int[] nums, int target) {
     Map<Integer, Integer> map = new HashMap<>();
     for (int i = 0;i < nums.length; i++) {
         int diff = target - nums[i];
         if (map.containsKey(diff)) {
            return new int[]{map.get(diff) ,i};
         } else {
            map.put(nums[i] , i);
         }
     }
     // 不存在这样的数
     return new int[]{-1 ,-1};
    }