前缀和以及二分法解题_前缀长度二分查找

1、寻找数组的中心索引

解法1：初始解法

思路： 长度为1的数组，中心索引一定是它本身的那个唯一元素，左右两边的和都为0。

长度为2的数组，除非两个元素都为0 那么这样才存在中心索引，且选最左边的0

长度大于等于2的数组：我们现在讨论普遍的情况，令索引 i 左边的值相加和索引右边的值相加的和作比较，相等的话直接返回i。太慢了！！！

public static int pivotIndex1(int[] nums) {
    if(nums.length == 1) return 0;
    if(nums.length == 2 && nums[0] == 0 && nums[nums.length-1] == 0){
        return 0;
    }
    if(nums.length >= 2){
        for(int i=0;i < nums.length;i++){
            int sum1 = 0;
            int sum2 = 0;
            for(int t = 0; t < i;t++){
                sum1 += nums[t];
            }
            for(int s = nums.length-1;s > i;s--){
                sum2 += nums[s];
            }
            if(sum1 == sum2){
                return i;
            }
        }
    }
    return -1;
}
//执行用时：519 ms, 在所有 Java 提交中击败了5.04%的用户
//内存消耗：38.8 MB, 在所有 Java 提交中击败了82.22%的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

解法2：

思路：利用前缀和进行解题

什么是前缀和？前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。

分析本题：这是一道前缀和的裸题

只需要用两个数组，前后处理两遍前缀和，再对两个前缀和数组的相同下标进行判别即可。

为了简化数组越界判断，我们通常会给前缀和数组多预留一位作为哨兵。这里由于要求数组前后 算上的前缀和。所以我们直接给数组多开两位即length = n+2

public int pivotIndex2(int[] nums) {
    int n = nums.length;
    int[] s1 = new int[n + 2], s2 = new int[n + 2];
    //正着的前缀和数组，注意这里的i 是从1 与 n 开始的
    for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + nums[i - 1];
    //反着的前缀和数组
    for (int i = n; i >= 1; i--) s2[i] = s2[i + 1] + nums[i - 1];
    for (int i = 1; i <= n; i++) {
        if (s1[i] == s2[i]) return i - 1;
    }
    return -1;
}
//执行用时: 2 ms
//内存消耗: 38.8 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解法3：

思路：转换思路解题，中心下标左右的元素相加之和相等，转换成——左边求和*2 + 中心索引值 = 总和；

public int pivotIndex(int[] nums) {
    //求总和
    int sum = 0;
    for(int i = 0;i<nums.length;i++){
        sum += nums[i];
    }
    //求索引左边的和
    int cur = 0;
    for(int i = 0;i < nums.length;++i){
        cur +=nums[i];
        //cur先加了，然后就是需要减一个多的中心索引值
        if(2*cur-nums[i] == sum) return i;
    }
    return -1;
}
//执行用时: 1 ms
//内存消耗: 39.2 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、搜索插入位置

解法一：(初识解法)

给定一个 排序数组 和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中， 返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。

public int searchInsert(int[] nums, int target) {
    int num = 0;
    //目标值存在
    for(int i = 0;i < nums.length;i++){
        if(nums[i] == target){
            num = i;
        }
    }
    //目标值不存在，寻找应该插入的位置
    if(num == 0){
        for(int i = 0;i<nums.length;i++){
            if(i == 0){
                if(target < nums[i]){
                    num = 0;
                }
            }
            if(i >=0 && i< nums.length-1){
                if(target > nums[i] && target < nums[i+1]){
                    num = i+1;
                }
            }else{
                if(target > nums[i]){
                    num = i+1;
                } 
            }
        }
    }
    return num;
}
//执行用时: 1 ms
//内存消耗: 37.9 MB
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

解法二：暴力解法

public int searchInsert(int[] nums, int target) {
    for(int i = 0; i < nums.length;i++){
        if(nums[i] >= target){
            return i;
        }
    }
return nums.length;
//执行用时: 0 ms
//内存消耗: 38 MB
1
2
3
4
5
6
7
8
9

解法三：二分法（题目给的是有序数组，无重复元素）

二分法详解

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

总结：二分法查找的常用格式

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = mid = left + (right - left) / 2;
        //等同于mid = (right + left) / 2，但是上面的写法可以防止溢出！！！
        //先记住防溢出写法！
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

注意： . . . 标记的部分是需要注意的细节问题

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。

二分查找算法的一个简单举例：寻找一个有序数组中的元素，有返回该数索引，没有就返回-1；

int binarySearch(int[] nums, int target) {
   int left = 0;
   int right = nums.length -1;
   while(left <= right){
       int mid = left + ((right-left)/2); //防止溢出
       if(nums[mid] == target){
           return mid;
       }else if(nums[mid] < target){
           left = mid +1;
       }else if(nums[mid] > target){
           rigth = mid -1;
       }
   }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15