寻找数组的中心索引

问题描述

  1. 给你一个整数数组 nums ，请计算数组的 中心下标 。
  3. 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
  5. 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
  7. 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
  8. // 实例一
  9. 输入：nums = [1, 7, 3, 6, 5, 6]
  10. 输出：3
  11. 解释：
  12. 中心下标是 3 。
  13. 左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
  14. 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
  16. // 实例二
  17. 输入：nums = [1, 2, 3]
  18. 输出：-1
  19. 解释：
  20. 数组中不存在满足此条件的中心下标。
  21. // 实例三
  22. 输入：nums = [2, 1, -1]
  23. 输出：0
  24. 解释：
  25. 中心下标是 0 。
  26. 左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
  27. 右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

解题

// 解法一：自己思路，功能全部实现（运行时间过长无法上传，哈哈~~~）
public int search1(int[] nums){
        int sum1 = 0;
        int sum2 = 0;
        int left=0,right = nums.length-1;
        int mid = (left+right)/2;
        for (int i=0;i<mid;i++){
            sum1 +=nums[i];
        }
        for (int i=mid+1;i<=right;i++){
            sum2 +=nums[i];
        }
        while (mid>0 && mid<right){

            if (sum1 == sum2){
                return mid;
            }else if (sum1 < sum2){
                sum1 += nums[mid];
                sum2 -= nums[mid+1];
                mid+= 1;

            }else if (sum1 > sum2){
                sum2 += nums[mid];
                sum1 -= nums[mid-1];
                mid-= 1;
            }
        }
        while (mid<=0 || mid>=right){
            if (sum1 == sum2){
                return mid;
            }
        }
        return -1;
    }
// 解法二：别人思路（确实牛逼）
// 先利用循环把数组和求出，然后再一个一个减的同时校验是否符合条件
public int search2(int[] nums){
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
        int left_sum = 0;
        for(int i=0;i<nums.length;i++){
            sum -= nums[i];
            if(left_sum == sum){
                return i;
            }
            left_sum += nums[i];
        }
        return -1;
    }

求数组各项的平方（有序排列）

问题描述

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

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

解题

// 解法一：
public int[] search(int[] nums){
        int left = 0;
        int right = nums.length-1;
        int[] result = new int[nums.length]; // 申请一份内存空间
        int index = result.length - 1;
        while (left <= right){
            if (nums[left]*nums[left] > nums[right]*nums[right]){
                result[index--] = nums[left]*nums[left];
                left++;
            }else {
                result[index--] = nums[right]*nums[right];
                right--;
            }
        }
        return result;
    }

// 方式二：（也就是方式一的简化版）
public int[] search(int[] nums){
        int left = 0;
        int right = nums.length-1;
        int[] result = new int[nums.length]; // 申请一份内存空间
        int index = result.length - 1;
        while (left <= right){
            if (nums[left]*nums[left] > nums[right]*nums[right]){
                result[index--] = nums[left]*nums[left++];
            }else {
                result[index--] = nums[right]*nums[right--];
            }
        }
        return result;
    }

求长度最小的子数组

问题描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解题

// 利用的是双指针，我们通常叫这种方法为“滑动窗口”
public int search2(int[] nums,int s){
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == Integer.MAX_VALUE ? 0 : result;
    }