1. 最小的k个数

  • 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
  1. 示例 1：
  3. 输入：arr = [3,2,1], k = 2
  4. 输出：[1,2] 或者 [2,1]
  5. 示例 2：
  7. 输入：arr = [0,1,2,1], k = 1
  8. 输出：[0]
  11. 限制：
  13. 0 <= k <= arr.length <= 10000
  14. 0 <= arr[i] <= 10000

思路：

  • 先进行排序
  • new 一个k个长度的数组

  • for循环或者使用数组copy截取给定数组中的前k个

    class Solution {
  public int[] getLeastNumbers(int[] arr, int k) {
      Arrays.sort(arr);
      int[] res = new int[k];
      for(int i=0;i<k;i++){
          res[i] = arr[i];
      }
      return res;
  }
}

    class Solution {
  public int[] getLeastNumbers(int[] arr, int k) {
      Arrays.sort(arr);
      return Arrays.copyOfRange(arr,0,k);
  }
}

    2. 连续子数组的最大和

  • 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 ``` 示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

1 <= arr.length <= 10^5 -100 <= arr[i] <= 100

<a name="4VdJe"></a>
### 思路：

- 使用动态规划
- 设动态规划列表dp
- 当dp[i-1]<0时，dp[i]=nums[i]；当dp[i-1]>=0时，dp[i]=nums[i]+dp[i-1]；

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i=1;i<nums.length;i++){
            nums[i] = Math.max(nums[i-1],0);
            res = Math.max(nums[i],res);
        }
        return res;
    }
}