代码随想录算法训练营Day2|数组2|双指针 滑动窗口

977.有序数组的平方

【简单题】【题目链接】

• 含负数的非递减数组，V字形数据，绝对值排序
• 思路一：二分找到abs最小值+双指针
• 思路二：预先开辟数组，直接双指针，从后往前填！
  惯性思维想的是思路一，但其实直接反过来排序用思路二不用预先找最小值

## 思路一中的找V字形中abs最小值位置，后续实现略
def findminabs(nums):
    if not nums:
        return None
    left,right = 0,len(nums)-1
    if nums[left]>=0:
        mid = 0
    else:
        while(left<=right):
            mid = left + (right-left)//2
            if nums[left]*nums[mid]>0:
                left = mid+1
            elif nums[right]*nums[mid]>0:
                right = mid-1
            elif nums[mid]==0:
                break
    return mid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left,right = 0,len(nums)-1
        ans = [0]*(right+1)
        index = right
        while(left<=right):
            if abs(nums[left])>=abs(nums[right]):
                ans[index] = nums[left]**2
                left += 1
            elif abs(nums[left])<abs(nums[right]):
                ans[index] = nums[right]**2
                right -= 1
            index-=1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

209.长度最小的子数组

【中等题】【题目链接】

• 滑动窗口解题
  第一次写出来的写法还可以精简

## 第一次的写法
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        SUM = 0
        N = len(nums)
        left,right = 0,0
        ans = float('inf')
        while(right<N):
            #while(SUM<target and right<N):   ##这里的while可以进行精简
                #SUM += nums[right]
                #right += 1
            SUM += nums[right] 
            right += 1
            while(SUM>=target):
                ans = min(ans,right-left)
                SUM -= nums[left]
                left += 1 
        return 0 if ans==float('inf') else ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

59.螺旋矩阵Ⅱ

【中等题】【题目链接】

• 考查数组操控能力