数组相关算法

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;
}

75. 颜色分类

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

public void sortColors(int[] nums) {
    int p1 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            if (i != p1)
                swap(nums, p1, i);
            p1++;
        }
    }

    for (int i = p1; i < nums.length; i++) {
        if (nums[i] == 1) {
            if (i != p1)
                swap(nums, p1, i);
            p1++;
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

125. 验证回文串

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

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

  public static boolean isPalindrome(String s) {
    int right = s.length() - 1;
    int left = 0;
    while (left < right) {
      char leftChar = s.charAt(left);
      while (!Character.isLetterOrDigit(leftChar) && left < right) {
        leftChar = s.charAt(++left);
      }
      char rightChar = s.charAt(right);
      while (!Character.isLetterOrDigit(rightChar) && left < right) {
        rightChar = s.charAt(--right);
      }
      if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
        return false;
      }
      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;
}

• 解法二：双指针

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. 移动零

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

进阶：

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

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

public void rotate(int[] nums, int k) {
    k = k % nums.length;
    int[] n = new int[k];
    if (k >= 0) {
        System.arraycopy(nums, nums.length - k, n, 0, k);
    }
    if (nums.length - k - 1 + 1 >= 0) {
        System.arraycopy(nums, 0, nums, k, nums.length - k - 1 + 1);
    }
    if (n.length >= 0) {
        System.arraycopy(n, 0, nums, 0, n.length);
    }
}

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;
    }
}