数据结构：数组

发表于 | 分类于

两数之和

  • 给一个整数数组nums和目标值target，找出和为目标值的两个整数的下标
  • [2,7,11,15] 9 => [0,1]

思路：

  1. 使用一个map将遍历过的数字存起来，{key: value}中，key是值，value是下标。
  2. 每次遍历在map中查找是否有key为target-nums[i]的值
  3. 如果取到，则条件成立，返回
  4. 如果没有取到，则将当前值为key，下标作为value存入map

js

1
2
3
4
5
6
7
8
9
10
11
12
function twoSum(nums, target) {
  let map = {};
  for (let i=0; i<nums.length; i++) {
    if(map[target-nums[i]] !== undefined) {
      return [map[target - nums[i]], i];
    } 
    else {
      map[nums[i]] = i;
    }
  }
  return [];
}

java

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0; i<nums.length;i++) {
      int complement = target - nums[i];
      if(map.containsKey(complement)) {
        return new int[] { map.get(complement), i };
      }
      map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
  }
}

三数之和

  • nums中存在三个元素a+b+c=0
  • [-1,0,1,2,-1,-4] => [[-1,0,1],[-1,-1,2]]

思路

  1. 首先将数组排序
  2. 对数组遍历，取当前遍历的数nums[i]为一个基准数，遍历数后面的数组（寻找数组）
  3. 在寻找数组中设定两个起点，最左侧的left(i+1)和最右侧的right(length-1)
  4. 判断nums[i]+nums[left]+nums[right]===0，如果成立的话加入结果数组，分别将left和right移动一位
  5. 结果大于0，right向左移动一位，向结果逼近
  6. 结果小于0，left向右移动一位，向结果逼近

js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function threeSum(nums) {
  let result = [];
  nums.sort((a,b) => a-b);
  for(let i=0;i<nums.length;i++) {
    if(i && nums[i] === nums[i-1]) {
      continue;
    }
    let left = i + 1;
    let right = nums.length -1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if(sum > 0) {
        right --;
      }
      else if(sum < 0) {
        left ++;
      }
      else {
        result.push([nums[i], nums[left++], nums[right--]]);
        while(nums[left] === nums[left-1]){
          left ++;
        }
        while(nums[right] === nums[right+1]) {
          right --;
        }
      }
    }
  }
  return result;
}

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
  public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    // 枚举a
    for (int first = 0; first < n; ++ first) {
      if(first > 0 && nums[first] == nums[first-1]) {
        continue;
      }
      //c 对应的指针指向最右端
      int third = n-1;
      int target = -nums[first];
      //枚举b
      for (int second = first + 1; second < n; ++second) {
        // 需要和上一次枚举的数不相同
        if (second > first + 1 && nums[second] == nums[second - 1]) {
          continue;
        }
        // 需要保证 b 的指针在 c 的指针的左侧
        while (second < third && nums[second] + nums[third] > target) {
          --third;
        }
        // 如果指针重合，随着 b 后续的增加
        // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
        if (second == third) {
           break;
        }
        if (nums[second] + nums[third] == target) {
          List<Integer> list = new ArrayList<Integer>();
          list.add(nums[first]);
          list.add(nums[second]);
          list.add(nums[third]);
          ans.add(list);
        }
      }
    }
    return ans;
  }
}