LeetCode字节跳动专题 - 数组和排序_超长数组排序

两数之和

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解法

用线性的时间复杂度来解决问题，那么就是说只能遍历一个数字，那么另一个数字呢，我们可以事先将其存储起来，使用一个 HashMap，来建立数字和其坐标位置之间的映射，我们都知道 HashMap 是常数级的查找效率，这样，我们在遍历数组的时候，用 target 减去遍历到的数字，就是另一个需要的数字了，直接在 HashMap 中查找其是否存在即可。

AC代码

public class Solution {
   
   public int[] twoSum(int[] nums, int target) {
   
       HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
       int[] res = new int[2];
       for (int i = 0; i < nums.length; ++i) {
   
           m.put(nums[i], i);
       }
       for (int i = 0; i < nums.length; ++i) {
   
           int t = target - nums[i];
           if (m.containsKey(t) && m.get(t) != i) {
   
               res[0] = i;
               res[1] = m.get(t);
               break;
           }
       }
       return res;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

解法

先将数组排序，使用 i，j，k 三个指针。i指向最小的数可能的位置，k 指向最大的数的位置，j 指向中间的数可能的位置。遍历原理核心为每次遍历会遇到得三种情况：
1.nums[i]+nums[j]==-nums[k]，此时说明刚好三数加一起等于 0，于是此时要把j向右拨一位，但此时nums[i]+nums[j] 变大了(nums[j] 变大的情况下)，所以同时也要把k向左拨。也即此时i++，k–;
2.nums[i]+nums[j]>-nums[k]，此时说明 nums[i]+nums[j]+nums[k]>0，所以k要向左拨，k–;
3.nums[i]+nums[j]<-nums[k]，此时说明 nums[i]+nums[j]+nums[k]<0，所以j要向右拨，j++;
当然，遍历的时候肯定会考虑重复等一些的情况，所以要加上邻位判断。比如在遍历第一种情况时，如果nums[j]==nums[j-1]，说明此时 j 已经考虑过了，直接 j++ 即可。

AC代码

class Solution {
   
public:
   vector<vector<int>> threeSum(vector<int>& nums) {
   
       vector<vector<int>> res;
       sort(nums.begin(), nums.end());
       if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {
   };
       for (int k = 0; k < nums.size(); ++k) {
   
           if (nums[k] > 0) break;
           if (k > 0 && nums[k] == nums[k - 1]) continue;
           int target = 0 - nums[k];
           int i = k + 1, j = nums.size() - 1;
           while (i < j) {
   
               if (nums[i] + nums[j] == target) {
   
                   res.push_back({
   nums[k], nums[i], nums[j]});
                   while (i < j && nums[i] == nums[i + 1]) ++i;
                   while (i < j && nums[j] == nums[j - 1]) --j;
                   ++i; --j;
               } else if (nums[i] + nums[j] < target) ++i;
               else --j;
           }
       }
       return res;
   }
};
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

最近三数之和

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解法

求最接近给定值的三数之和即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量 diff 用来记录差的绝对值，然后我们还是要先将数组排个序，然后开始遍历数组，思路跟那道三数之和很相似，都是先确定一个数，然后用两个指针 left 和 right 来滑动寻找另外两个数，每确定两个数，我们求出此三数之和，然后算和给定值的差的绝对值存在 newDiff 中，然后和 diff 比较并更新 diff 和结果 closest 即可，代码如下：

AC代码

class Solution {
   
public
1
2