数组相关算法

目录

• 1. 两数之和
• 53. 最大子序和
• 75. 颜色分类
• 124.验证回文串
• 167. 两数之和 II - 输入有序数组
• 189.旋转数组
• 283.移动0
• 303.区域和检索 - 数组不可变
• 643.有序数组的平方

题目

1. 两数之和

给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。

• 解法一：双重循环

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

• 解法二：使用HashMap

public static int[] twoSum1(int[] nums, int target) {
  Map<Integer, Integer> map = new HashMap<>();
  for (int i = 0; i < nums.length; i++) {
    if (map.containsKey(target - nums[i])) {
      return new int[] { map.get(target - nums[i]), i };
    }
    map.put(nums[i], i);
  }
  return null;
}

53. 最大子序和

public int maxSubArray(int[] nums) {
    int res = nums[0];
    int sum = 0;
    for (int num : nums) {
        if (sum > 0)
            // 如果sum>0,则sum+num可能会更大
            sum += num;
        else
            // 如果sum<=0,则sum+num一定小于等于num，所以，让sum直接等于num是当前最大值
            sum = num;
        // 把每次最大的结果都保存到res中
        res = Math.max(res, sum);
    }
    return res;
}

75. 颜色分类

给定一个包含红色、白色和蓝色，一共n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

public class Solution {
    /**
     * 解题思路：
     * <p>
     * 1.通过双指针第一趟扫描0号球，快指针遍历，慢指针指向第一个非0位置，等到快指针扫
     * 描到0后与慢指针交换位置。直到快指针遍历完整个数组，此时慢指针指向第一个非0位置
     * 2. 第二趟从上一趟慢指针位置开始遍历，扫描1号球，思想与第一步类似。完成此次遍历
     * 与交换后便完成了三色球的排序
     */
    public void sortColors(int[] nums) {
        // 慢指针
        int p = 0;
        // i 为快指针
        for (int i = 0; i < nums.length; i++) {
            // 遍历到0号球
            if (nums[i] == 0) {
                // p 一定是小于等于i的，等于i时候说明两个指针指向同一个小球，不需要交换
                if (p < i)
                    // 将i处的0号球与慢指针位置的球交换
                    swap(nums, p, i);
                // 满指针加1，指向下一个非0球
                p++;
            }
        }
        // 第二趟查找1号球
        for (int i = p; i < nums.length; i++) {
            if (nums[i] == 1) {
                if (p < i)
                    swap(nums, p, i);
                p++;
            }
        }
    }

    private void swap(int[] nums, int n, int m) {
        int temp = nums[n];
        nums[n] = nums[m];
        nums[m] = temp;
    }
}

125. 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

public class Solution {
    /**
     * 解题思路：
     * 双指针法，左指针指向起始位置，右指针指向末尾位置。左指针如果不是字母或者数字就不断加1，
     * 右指针如果不是字母或者数字就不断减1。左右指针都指向数字的时候比较两个字符是否相等（忽略大小写），
     * 如果不相等，则返回false，如果相等，则继续比较下一个，直到所有字符对比完成，则返回true。
     * 
     * 
     */
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        // 循环终止条件，左指针小于右指针
        while (left < right) {
            // 左指针如果指向的不是字母或数字则不断加1，需要保证left小于right
            // 注意这里 Character.isLetterOrDigit 的API
            while (!Character.isLetterOrDigit(s.charAt(left)) && left < right) {
                left++;
            }
            // 右指针如果指向的不是字母或数字，则不断减1，同样需要保证左指针小于右指针
            while (!Character.isLetterOrDigit(s.charAt(right)) && left < right) {
                right--;
            }
            // 忽略大小写，比较左右指针指向的字符是否相等，注意Character.toLowerCase的API
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                // 不相等，则不是回文字符，返回false
                return false;
            }
            // 完成一次对比左指针加1，右指针减1
            left++;
            right--;
        }
        return true;
    }
}

167. 两数之和 II - 输入有序数组

给定一个已按照 非递减顺序排列 的整数数组numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

• 解法一：暴力法

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

• 解法二：双指针

/**
 * 由于是一个有序数组，因此可以使用双指针，一个指针指向数组头，另一个指针指向数组尾。如果两个指针位置的元素相加小于target
 * 那么就让左指针向右移动一次，如果相加之和大于target，则让右指针向左移动一次，如果相加等于target，则返回向指针的位置即可。
 * 边界条件是左指针小于右指针
 */
public int[] twoSum(int[] numbers, int target) {
    int p1 = 0, p2 = numbers.length - 1;
    while (p1 <= p2) {
        if (numbers[p1] + numbers[p2] > target) {
            p2--;
        } else if (numbers[p1] + numbers[p2] < target) {
            p1++;
        } else {
            return new int[]{p1 + 1, p2 + 1};
        }
    }

    return new int[]{-1,-1};
}

189. 旋转数组

给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

你可以使用空间复杂度为O(1) 的原地算法解决这个问题吗？

public void rotate(int[] nums, int k) {
     k = k % nums.length;
    int[] n = new int[k];
    for (int i = 0; i < k; i++) {
        n[i] = nums[nums.length - k + i];
    }

    for (int i = nums.length - k - 1; i >= 0; i--) {
        nums[i + k] = nums[i];
    }
    for (int i = 0; i < n.length; i++) {
        nums[i] = n[i];
    }
}

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:

必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。

/**
 * 用两个指针同时从0位置开始移动，一个快指针为i,一个慢指针j。快指针每次都移动，慢指针只有在指向的位置不等于0的时候
 * 才移动一次，并将快指针指向的值赋值给慢指针的位置。这样当快指针j指向数组最后一个元素的时候，慢指针i指向位置之后的
 * 所有元素都应该是0，因此，从慢指针i的位置开始遍历，将所有值改为0。
 * 
 */
    public static void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
            }
        }

        for (int i = j; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

303. 区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例：

输入： ["NumArray", "sumRange", "sumRange", "sumRange"] [-2, 0, 3, -5, 2, -1, [0, 2], [2, 5], [0, 5]] 输出： [null, 1, -1, -3]

解释： NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

• 解法1

class NumArray {
    private final int[] nums;
    public NumArray(int[] nums) {
       this.nums=nums;
    }
    
    public int sumRange(int left, int right) {
        if(nums==null){
            return 0;
        }
        int sum = 0;
        for(;left<=right;left++){
            sum += nums[left];
        }
        return sum;
    }
}

• 解法2

public class NumArray {
    private final int[] sums;

    public NumArray(int[] nums) {
        int n = nums.length;
        sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + sums[i + 1];
        }
    }

    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}

643. 子数组最大平均数 I

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

  public double findMaxAverage(int[] nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) {
      sum += nums[i];
    }
    if (nums.length == k) {
      return (double) sum / k;
    }
    int maxSum = sum;
    if (k == 1) {
      for (int i = 1; i < nums.length - 1; i++) {
        maxSum = Math.max(maxSum, nums[i]);
      }
      return maxSum;
    }
    for (int i = 0; i < nums.length - k; i++) {
      sum = sum - nums[i] + nums[i + k];
      maxSum = Math.max(maxSum, sum);
    }
    return (double) maxSum / k;
  }

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

public int[] sortedSquares(int[] nums) {
    if (nums[0] >= 0) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        return nums;
    } else if (nums[nums.length - 1] <= 0) {
        int[] newArray = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            newArray[i] = nums[nums.length - 1 - i] * nums[nums.length - 1 - i];
        }
        return newArray;
    } else {
        int[] newArray = new int[nums.length];
        int i = 0, j = nums.length - 1, k = nums.length - 1;
        while (i <= j) {
            int ii = nums[i] * nums[i];
            int jj = nums[j] * nums[j];
            if (ii >= jj) {
                newArray[k--] = ii;
                i++;
            } else {
                newArray[k--] = jj;
                j--;
            }
        }
        return newArray;
    }
}