寻找数组的中心索引

给你一个整数数组 nums，请编写一个能够返回数组 “中心下标” 的方法。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心下标，返回 -1 。如果数组有多个中心下标，应该返回最靠近左边的那一个。
注意：中心下标可能出现在数组的两端。

难度：简单

示例 1：

  1. 输入：nums = [1, 7, 3, 6, 5, 6]
  2. 输出：3
  3. 解释：
  4. 中心下标是 3 。
  5. 左侧数之和 (1 + 7 + 3 = 11)，
  6. 右侧数之和 (5 + 6 = 11) ，二者相等。

示例 2：

  1. 输入：nums = [1, 2, 3]
  2. 输出：-1
  3. 解释：
  4. 数组中不存在满足此条件的中心下标。

示例 3：

  1. 输入：nums = [2, 1, -1]
  2. 输出：0
  3. 解释：
  4. 中心下标是 0 。
  5. 下标 0 左侧不存在元素，视作和为 0 ；
  6. 右侧数之和为 1 + (-1) = 0 ，二者相等。

提示：

  1. nums 的长度范围为 [0, 10000]。
  2. 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。

方式1：
思路：遍历数组中每个元素，当某个元素之前的和等于 之后的和返回元素的下标，否则返回-1;
实现：

  1. class Solution {
  2.     public int pivotIndex(int[] nums) {
  3.         int result = -1;
  4.         for (int i=0;i < nums.length; i++) {
  5.             // 当前下标前的和
  6.             int sumBefore = 0;
  7.             // 当前下标后的和
  8.             int sumAfter = 0;
  9.             for (int j = 0; j < nums.length; j++) {
  10.                 if (j < i) {
  11.                     sumBefore += nums[j];
  12.                 } else if (j > i) {
  13.                     sumAfter += nums[j];
  14.                 } 
  16.             }
  17.             if (sumBefore == sumAfter) {
  18.                 return i;
  19.             }
  20.         }
  21.         return result;
  22.     }
  23. }

时间复杂度：数组 - 图1

方式2：前缀和
思路：记数组的全部元素之和为total，当遍历到第 i 个元素时，设其左侧元素之和为sum，则其右侧元素之和为 数组 - 图2，左右元素相等即为数组 - 图3，即数组 - 图4
实现：

  1. class Solution {
  2.     public int pivotIndex(int[] nums) {
  3.         int total = Arrays.stream(nums).sum();
  4.         int sum = 0;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             if (2 * sum + nums[i] == total) {
  7.                 return i;
  8.             }
  9.             sum += nums[i];
  10.         }
  11.         return -1;
  12.     }
  13. }

时间复杂度：数组 - 图5

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

难度：简单

示例 1:

  1. 输入: [1,3,5,6], 5
  2. 输出: 2

示例 2:

  1. 输入: [1,3,5,6], 2
  2. 输出: 1

示例 3:

  1. 输入: [1,3,5,6], 7
  2. 输出: 4

示例 4:

  1. 输入: [1,3,5,6], 0
  2. 输出: 0

方式1：
思路：二分法查找

  • 先设定左下标left和右下标right，再计算中间下标mid。
  • 每次根据nums[mid]和target之间的大小进行判断，相等则直接返回下标，nums[mid] < target则left右移，nums[mid] < target则right左移。
  • 查找结束如果没有相等值则返回left，该值为插入位置。

实现：

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.         int left = 0;
  4.         int right = nums.length - 1;
  5.         int mid = 0;
  6.         while (left <= right) {
  7.            mid = (left + right) / 2 ;
  8.            if (nums[mid] == target) {
  9.                 return mid;
  10.            } else if (nums[mid] > target) {
  11.                 right = mid - 1;
  12.            } else {
  13.                 left = mid + 1;
  14.            }
  15.         }
  16.         return left;
  17.     }
  18. }

时间复杂度：数组 - 图6

合并区间

以数组intervals表示若干个区间的集合，其中单个区间为。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

  1. 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
  2. 输出：[[1,6],[8,10],[15,18]]
  3. 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

  1. 输入：intervals = [[1,4],[4,5]]
  2. 输出：[[1,5]]
  3. 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

  • 数组 - 图7
  • 数组 - 图8
  • 数组 - 图9

力扣 (LeetCode)-LeetBook数组和字符串