C语言重构【1477】找两个和为目标值且不重叠的子数组

港控/mmm° 2022-11-08 14:23 93阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你一个整数数组 arr 和一个整数值 target 。
    
    请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。
    
    请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。
    
     
    
    示例 1：
    
    输入：arr = [3,2,2,4,3], target = 3
    输出：2
    解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。
    示例 2：
    
    输入：arr = [7,3,4,7], target = 7
    输出：2
    解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。
    示例 3：
    
    输入：arr = [4,3,2,6,2,3,4], target = 6
    输出：-1
    解释：我们只有一个和为 6 的子数组。
    示例 4：
    
    输入：arr = [5,5,4,4,5], target = 3
    输出：-1
    解释：我们无法找到和为 3 的子数组。
    示例 5：
    
    输入：arr = [3,1,1,1,5,1,2,1], target = 3
    输出：3
    解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。
     
    
    提示：
    1 <= arr.length <= 10^5
    1 <= arr[i] <= 1000
    1 <= target <= 10^8

#### 方案： ####

*  我太菜了，别人双指针完事，俺要四指针，俩滑动窗口才能搞定
 *  题目的意思是找俩字数组（元素必须连续的那种，且不能重叠），然后思路就是左右开工，俩滑动窗口，处理下边界的问题，就可以了。
 *  每次选择哪个框动的时候，有点贪心思想，就是交大的动，这样有更多的减少空间（俺承认有赌的成分）

class Solution
    { 
    public:
        int minSumOfLengths(vector<int> &arr, int target)
        { 
            //滑动窗口算法
            int len = arr.size();
            if (len == 1)
                return -1;
            //在数组两侧用两个滑动窗口
            //其中left1和right2取值界限，
            int left1 = len - 1, left2 = len - 1, right1 = 0, right2 = 0;
            // 用于判断什么时候该停了
            int border1 = right1, border2 = left1;
            //这俩是记录最小值用的
            int mr = len, ml = len;
            int sumr = arr[0];
            int suml = arr[len - 1];
            //true=左动
            int lturn = 1, rturn = 1, turn = 1;
    
            while (left1 > border1 && right2 < border2)
            { 
    
                if (rturn == 0 && lturn == 1)
                    turn = 0;
                else if (rturn == 1 && lturn == 0)
                    turn = 1;
                else if (rturn == 0 && lturn == 0)
                    break;
                // else if(lturn==1) turn=0;
    
                //如果mr>=ml 动右边
                if (turn == 1)
                { 
                    if (sumr < target)
                    { 
                        right2++;
                        sumr += arr[right2];
                    }
                    else if (sumr >= target)
                    { 
                        if (sumr == target)
                        { 
                            mr = min(mr, right2 - right1 + 1);
                            border1 = right2;
                            if (mr < ml)
                                turn = 0;
                        }
                        sumr -= arr[right1];
    
                        right1++;
                        if (right2 < right1)
                        { 
                            right2 = right1;
                            sumr += arr[right1];
                        }
                    }
                    if (right2 > border2 - 1 || right1 > border2 - 1)
                    { 
                        //触碰到边界
                        rturn = 0;
                        right1 = border1;
                        right2 = border1;
                    }
                }
                //如果mr<ml 动左边
                else if (turn == 0)
                { 
                    if (suml < target)
                    { 
    
                        left1--;
                        suml += arr[left1];
                    }
                    else if (suml >= target)
                    { 
                        if (suml == target)
                        { 
                            ml = min(ml, left2 - left1 + 1);
                            border2 = left1;
                            if (ml < mr)
                                turn = 1;
                        }
                        suml -= arr[left2];
    
                        left2--;
                        if (left2 < left1)
                        { 
                            left1 = left2;
                            suml += arr[left1];
                        }
                    }
                    if (left1 < border1 + 1 || left2 < border1 + 1)
                    { 
                        //触碰到边界
                        lturn = 0;
                        left1 = border2;
                        left2 = border2;
                    }
                }
            }
            // return m2 < len ? m1 + m2 : -1;
            return ml < len && mr < len ? mr + ml : -1;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode