数组的经典算法题

移动数组

  1. //给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 
  2. //
  3. // 示例: 
  4. //
  5. // 输入: [0,1,0,3,12]
  6. //输出: [1,3,12,0,0] 
  7. //
  8. // 说明: 
  9. //
  10. // 
  11. // 必须在原数组上操作，不能拷贝额外的数组。 
  12. // 尽量减少操作次数。 
  13. // 
  14. // Related Topics 数组 双指针
  17. //leetcode submit region begin(Prohibit modification and deletion)
  18. class Solution {
  19.     public void moveZeroes(int[] nums) {
  20.         //1 读懂题目要求：
  21.         //  将数组中 0 移动到数组的末尾，同时保持非零元素的相对顺序
  22.         //  必须在原数组上操作，不能拷贝额外的数组
  23.         //  尽量减少操作次数
  24.         //2 解题思路：
  25.         // 解法1： loop数组非0的当前loop count+1 一次从0开始替换不为0的元素，然后在loop 从count开始剩余的元素都是0
  26. //        int count = 0;
  27. //        for (int i = 0; i < nums.length; i++) {
  28. //            if (nums[i] != 0) {
  29. //                nums[count++] = nums[i];
  30. //            }
  31. //        }
  32. //        for (int i = count; i <nums.length ; i++) {
  33. //            nums[i] = 0;
  34. //        }
  35.         // 解法2： 上述使用了两个循环还可以在进行优化：通过类似的两个指针快慢指针，进行替换操作
  36.         for (int i = 0,count = 0; i < nums.length; i++) {
  37.             if (nums[i] != 0){
  38.                 //快慢指针进行元素替换操作
  39. //                int temp = nums[i];
  40. //                nums[i] = nums[count];
  41. //                nums[count] = temp;
  42. //                count++;
  43.                 //以上替换操作还可以在优化 可以将temp优化掉
  44.                 if (count != i){
  45.                     nums[count] = nums[i];
  46.                     nums[i] = 0;
  47.                 }
  48.                 count++;
  49.             }
  50.         }
  51.     }
  52. }
  53. //leetcode submit region end(Prohibit modification and deletion)

合并排序数组

  1. //给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。 
  2. //
  3. // 初始化 A 和 B 的元素数量分别为 m 和 n。 
  4. //
  5. // 示例: 
  6. //
  7. // 输入:
  8. //A = [1,2,3,0,0,0], m = 3
  9. //B = [2,5,6],       n = 3
  10. //1 2 3 2 5 6
  11. //输出: [1,2,2,3,5,6] 
  12. // Related Topics 数组 双指针
  15. import java.util.Arrays;
  17. //leetcode submit region begin(Prohibit modification and deletion)
  18. class Solution {
  19.     public void merge(int[] A, int m, int[] B, int n) {
  20. //        solutionOne(A,m,B,n);
  21.     }
  23.     /**
  24.      * 逆向双指针解法：双指针从m n的位置来时逆向查找 并添加到数组的尾部，注意
  25.      * 已经排好序的数组哪个大就会在最后,原地修改数组A 而不用在开一个额外的数组空间
  26.      *
  27.      * @param A
  28.      * @param m
  29.      * @param B
  30.      * @param n
  31.      */
  32.     public void solutionS(int[] A, int m, int[] B, int n) {
  33.         int pa = m - 1;
  34.         int pb = n - 1;
  35.         int t = m + n - 1;
  36.         int cur = 0;
  37.         while (pa >= 0 || pb >= 0) {
  38.             if (pa == -1){
  39.                 cur = B[pb--];
  40.             }else if (pb == -1){
  41.                 cur = A[pa--];
  42.             }else if (A[pa] > B[pb]){
  43.                 cur = A[pa--];
  44.             } else {
  45.                 cur = B[pb--];
  46.             }
  47.             A[t--] = cur;
  48.         }
  49.     }
  51.    /**
  52.      * 双指针解法:注意题目描述的是A B 已经被排序利用这个性质来解答，注意双指针解法
  53.      * 在数组中必须是排好序的数组,既然A B 已经排好序了，那么一个指针指向A 的0下标pa=0， 一个
  54.      * 指针指向B的0 下标pb=0，判断A[pa] B[pb]的大小 小的那个放到一个新的数组中，如果pa==m||pb==n 则循环终止
  55.      * @param A
  56.      * @param m
  57.      * @param B
  58.      * @param n
  59.      */
  60.     public void solutionTwo(int[] A, int m, int[] B, int n){
  61.         int pa=0,pb=0;
  62.         int[] result = new int[m+n];
  63.         int count = 0;
  64.         int cur = 0;
  65.         while (pa < m || pb < n){
  66.             if (pa == m){
  67.                 cur = B[pb++];
  68.             }else if (pb == n){
  69.                 cur = A[pa++];
  70.             }else if (A[pa] < B[pb]){
  71.                 cur = A[pa++];
  72.             }else{
  73.                 cur = B[pb++];
  74.             }
  75.             result[count++] = cur;
  76.         }
  77.         for (int i = 0; i < result.length; i++) {
  78.             A[i] = result[i];
  79.         }
  80.     }
  82.     /**
  83.      * 暴力破解法：
  84.      * 思路：既然题目要求要合并到A中，首先将B的数据合并到A中，然后在对A进行排序
  85.      * @param A
  86.      * @param m
  87.      * @param B
  88.      * @param n
  89.      */
  90.     public void solutionOne(int[] A, int m, int[] B, int n){
  91.         int num = m + n;
  92.         //1 将B的数据添加到A中 1 2 3 2 5 6 直接从m开始向A中添加数据
  93.         //边界
  94.         //[0,0]
  95.         //0
  96.         //[1]
  97.         //1
  98.         //错误用例：
  99.         //[4,0,0,0,0,0]
  100.         //1
  101.         //[1,2,3,5,6]
  102.         //5
  103.         for (int i = 0; i < n; i++) {
  104.             A[m + i] = B[i];
  105.         }
  106.         //2 排序A中的数据 通过快慢双指针进行 1 2 3 2 5 6
  107.         for (int i = 0; i < num - 1; i++) {
  108.             for (int j = i + 1; j < num; j++) {
  109.                 if (A[i] > A[j]) {
  110.                     int temp = A[j];
  111.                     A[j] = A[i];
  112.                     A[i] = temp;
  113.                 }
  114.             }
  115.         }
  116.     }
  117. }
  118. //leetcode submit region end(Prohibit modification and deletion)

两数之和

  1. //给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 
  2. //
  3. // 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 
  4. //
  5. // 示例: 
  6. //
  7. // 给定 nums = [2, 7, 11, 15], target = 9
  8. //
  9. //因为 nums[0] + nums[1] = 2 + 7 = 9
  10. //所以返回 [0, 1]
  11. // 
  12. // Related Topics 数组 哈希表
  15. //leetcode submit region begin(Prohibit modification and deletion)
  16. class Solution {
  17.     public int[] twoSum(int[] nums, int target) {
  18.         Map<Integer,Integer> map = new HashMap<>();//记录所有数组值和下标
  19.         for(int i=0;i<nums.length;i++){
  20.             int result = target - nums[i];
  21.             if(map.containsKey(result) && map.get(result) != i){
  22.                 return new int[]{map.get(result),i};
  23.             }else{
  24.                 map.put(nums[i],i);
  25.             }
  26.         }
  27.         return new int[]{};
  28.     }
  29. }
  30. //leetcode submit region end(Prohibit modification and deletion)

三数之和

  1. //给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复
  2. //的三元组。 
  3. //
  4. // 注意：答案中不可以包含重复的三元组。 
  5. //
  6. // 
  7. //
  8. // 示例： 
  9. //
  10. // 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
  11. //
  12. //满足要求的三元组集合为：
  13. //[
  14. //  [-1, 0, 1],
  15. //  [-1, -1, 2]
  16. //]
  17. // 
  18. // Related Topics 数组 双指针
  21. import java.util.ArrayList;
  22. import java.util.Arrays;
  23. import java.util.List;
  25. //leetcode submit region begin(Prohibit modification and deletion)
  26. class Solution {
  27.     public List<List<Integer>> threeSum(int[] nums) {
  28.         List<List<Integer>> lists = new ArrayList<>();
  29.         if(nums == null || nums.length < 3) return lists;
  30.         // 假设输入：[-1, 0, 1, 2, -1, -4]
  31.         //先对数组进行排序 数组一般的解法使用双指针解法 要使用双指针解法就必须是排好序的数组
  32.         Arrays.sort(nums);//[-4,-1,-1,0,1,2]
  33.         //数组最大的下标
  34.         int len = nums.length - 1;
  35.         //判断边界值
  36.         if (nums[0] > 0 || nums[len] < 0) {//如果最小值大于0 那么不可能有相加等于0的，如果最大值<0 那么整个数组的值都是小于0 那么也不可能得到结果
  37.             return lists;
  38.         }
  39.         //[-4,-1,-1,0,1,2]
  40.         // L            R
  41.         // i = L+1
  42.         for (int i = 0; i < nums.length - 2; i++) {
  43.             //判断 num[i] 和 num[i+1]是否重复
  44.             if (i > 0 && nums[i] == nums[i - 1]) continue;
  45.             int L = i + 1;
  46.             int R = nums.length - 1;
  47.             while (L < R) {
  48.                 int result = nums[L] + nums[R] + nums[i];
  49.                 if (result < 0) {
  50.                     //如果得到的结果小于0则说明L要完右移动 增大值 同时要判断L是否重复
  51.                     L++;
  52.                 } else if (result > 0) {
  53.                     //如果得到的结果大于0则说明R要往左移动 减小值 同时要判断R是否重复
  54.                     R--;
  55.                 } else {
  56.                     lists.add(Arrays.asList(nums[i], nums[L], nums[R]));
  57.                     //==0 说明得到结果了 同时还得去重
  58.                     while (L < R && nums[L] == nums[L + 1]) L++;
  59.                     L++;
  60.                     while (L < R && nums[R] == nums[R - 1]) R--;
  61.                     R--;
  62.                 }
  63.             }
  64.         }
  65.         return lists;
  66.     }
  67. }
  68. //leetcode submit region end(Prohibit modification and deletion)

数组算法解题思路

  • 排序数组
  • 双指针
  • 哈希表