【LeetCode力扣】189 53 轮转数组 | 最大子数组和

梦里梦外; 2024-02-20 09:54 15阅读 0赞

**目录**

1、189. 轮转数组

1.1、题目介绍

1.2、解题思路

2、53. 最大子数组和

2.1、题目介绍

2.2、解题思路

![0193ef4e293a4a9b95a82a9713de3250.gif][]

![397a0f8626f348dab2dcd2b46f16cefb.png][]

## 1、189. 轮转数组 ##

### 1.1、题目介绍 ###

**原题链接：**[189. 轮转数组 - 力扣（LeetCode）][189. _ - _LeetCode]

![e06c38591418471fbe770069dea0baf0.png][]

**示例 1:**

> **输入:** nums = \[1,2,3,4,5,6,7\], k = 3  
> **输出:** \[5,6,7,1,2,3,4\]  
> **解释:**  
> 向右轮转 1 步: \[7,1,2,3,4,5,6\]  
> 向右轮转 2 步: \[6,7,1,2,3,4,5\]  
> 向右轮转 3 步: \[5,6,7,1,2,3,4\]

**示例 2:**

> **输入：**nums = \[-1,-100,3,99\], k = 2  
> **输出：**\[3,99,-1,-100\]  
> **解释:**  
> 向右轮转 1 步: \[99,-1,-100,3\]  
> 向右轮转 2 步: \[3,99,-1,-100\]

**提示：**

>  *  1 <= nums.length <= 10^5
>  *  \-2^31 <= nums\[ i \] <= (2^31)-1
>  *  0 <= k <= 10^5

### 1.2、解题思路 ###

**方法一：** **使用额外的数组**

> 我们可以使用额外的数组来将每个元素放至正确的位置。用 len 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k) % len 的位置，最后将新数组拷贝至原数组即可。

**代码实现：**

class Solution {
        public void rotate(int[] nums, int k) {
            int len = nums.length;
            int[] tmp = new int[len];
            for(int i = 0; i < len; i++) {
                tmp[(i+k)%len] = nums[i];
            }
    
            for(int i = 0; i< len; i++) {
                nums[i] = tmp[i];
            }
        }
    }

**复杂度分析**

>  *  时间复杂度： O(n)，其中 n 为数组的长度。
>  *  空间复杂度： O(n)。

**方法二：整体移动**

> k = 3 就相当于最右边的3个数整体移到了最左边。

![2f3c2ca6963d4e00b04ff2b6201a1470.png][]

![33e4859dab664abbbcc67890730f3a78.png][]

![92482e1c19e848cfb50d26440aefc14b.png][]

**代码实现：**

class Solution {
        public void rotate(int[] nums, int k) {
            int len = nums.length;
            int[] tmp = new int[k];
            k = k % len;   //旋转一周等于原来数组，因此首先需要就行k%len操作
            for(int i = len - k, index = 0; i < len; i++,index++) {   //使用tmp数组保存需要旋转的元素
                tmp[index] = nums[i];
            }
    
            for(int i = len - 1 - k; i >= 0; i--) {  //将不需要旋转的元素整体向后移动
                nums[i + k] = nums[i];
            }
    
            for(int i = 0; i < k; i++) {    //将旋转的元素依次放到最前面
                nums[i] = tmp[i];
            }
        }
    }

**复杂度分析** ：

>  *  时间复杂度： O(n)，其中 n 为数组的长度。
>  *  空间复杂度： O(1)，因为只用到了有限空间k。

## 2、53. 最大子数组和 ##

### 2.1、题目介绍 ###

**原题链接：**[53. 最大子数组和 - 力扣（LeetCode）][53. _ - _LeetCode]

![df26058ccba84d4cbb19d022422e6d8b.png][]

**示例 1：**

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

**示例 2：**

> **输入：**nums = \[1\]  
> **输出：**1

**示例 3：**

> **输入：**nums = \[5,4,-1,7,8\]  
> **输出：**23

**提示：**

>  *  1 <= nums.length <= 105
>  *  \-104 <= nums\[ i \] <= 104

### 2.2、解题思路 ###

**贪心算法：**

> 从头开始对数组进行累加和，当之前的和小于0时，则丢弃之前的和，即将和设为0，再继续结算和，然后和依然小于0，则继续丢弃，同时记录每次算出的最大和。

**图解说明：**

![3ede7cbdb034417d8e03aa2bc7542dae.png][]

![314343e0623d4ce5a2666cf7ef81a10b.png][]

![4ca93468f792429f94e706790d8d6a0a.png][]

![8efd2541119841699161de8ffdb2e30d.png][]

![d5f05b9f1f79484ba551de79cb9d5c22.png][]

> 按照这个规律继续执行，最后可以得出最大和为6，即为答案。

**代码实现：**

class Solution {
        public int maxSubArray(int[] nums) {
            int maxSum = nums[0];
            int sum = 0;
            for(int x : nums) {
                if(sum >= 0) {
                    sum += x;
                }else{    //贪心思想：如果之前的和小于0，则丢弃之前的和，再重新计算和
                    sum = 0;
                    sum += x;
                }
                maxSum = Math.max(maxSum,sum);
            }
            return maxSum;
        }
    }

**复杂度分析：**

>  *  时间复杂度： O(n)，只遍历一次数组。
>  *  空间复杂度： O(1)，只使用了常数空间。

更多【LeetCode刷题】 推荐：

[【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a02fa538033d4336b89bf0e9f46ce76b.png][LeetCode_234 _ _ _ _ _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133958602_spm_1001.2014.3001.5502]  
[【LeetCode力扣】86. 分隔链表-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c12db07a83b84e8c98aa02fd9559df16.png][LeetCode_86. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133942678_spm_1001.2014.3001.5502]

[【LeetCode力扣】297. 二叉树的序列化与反序列化-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/e409dad003c54ebf9f8aef73c28d2ee6.png][LeetCode_297. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133827375_spm_1001.2014.3001.5502]

![23330a8d89384e4d8eab31428e3f4149.gif][]

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

[0193ef4e293a4a9b95a82a9713de3250.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a64f423d32924888912124cb3a359ac2.png
[397a0f8626f348dab2dcd2b46f16cefb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/48a865f60ba844b9b5fd29cc8c0e8541.png
[189. _ - _LeetCode]: https://leetcode.cn/problems/rotate-array/submissions/477930156/?envType=study-plan-v2&envId=top-100-liked
[e06c38591418471fbe770069dea0baf0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/7256c64ae488495cb52f3efd241bc6d9.png
[2f3c2ca6963d4e00b04ff2b6201a1470.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/1ea98ce86cdb4e19b4ead17cdda7a3a7.png
[33e4859dab664abbbcc67890730f3a78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/b6d0b47124bf4a75af74153583e6d95d.png
[92482e1c19e848cfb50d26440aefc14b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/220652a586e24a188ee1ea5ca2c0673a.png
[53. _ - _LeetCode]: https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
[df26058ccba84d4cbb19d022422e6d8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/199f5db3aaa04ce4b00c9d0e09812e90.png
[3ede7cbdb034417d8e03aa2bc7542dae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/9d1d01b975ef47388713a63b5dac0aa4.png
[314343e0623d4ce5a2666cf7ef81a10b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c388bf43de5546e089a2ece6731e4a5a.png
[4ca93468f792429f94e706790d8d6a0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a4ab5c47622f4a2cb9a73f5e946146f0.png
[8efd2541119841699161de8ffdb2e30d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/7267635b7cd142edbcd420e5c5c2f516.png
[d5f05b9f1f79484ba551de79cb9d5c22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/0b3b9e20b9e94c978a12c9ed43c9de5a.png
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[LeetCode_234 _ _ _ _ _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133958602_spm_1001.2014.3001.5502]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a02fa538033d4336b89bf0e9f46ce76b.png
[LeetCode_86. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133942678_spm_1001.2014.3001.5502]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c12db07a83b84e8c98aa02fd9559df16.png
[LeetCode_297. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133827375_spm_1001.2014.3001.5502]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/e409dad003c54ebf9f8aef73c28d2ee6.png
[23330a8d89384e4d8eab31428e3f4149.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/9dfa210303cb4cb9acb1773839f5667c.png