【LeetCode】面试题57 - II. 和为s的连续正数序列 LCOF2020年3月6日

小灰灰 2021-06-10 20:38 187阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

其实有数学方法，我实在是不太会。。。  
于是我选择了滑动窗口来解决这个问题

### 怎么用滑动窗口 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]

*  主要是解决滑动窗口移动得问题，左右端点如何移动

1.  如果 `i-j` 的和值相加大于 `target` 得时候，左边界向右移动
2.  如果 `i-j` 的和值相加小于 `target` 得时候，右边界向右移动
3.  如果 `i-j` 的和值相加等于 `target` 得时候，左边界向右移动，这时状态又回到了小于 `target` 的时候

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 2]

### code ###

class Solution { 
        public int[][] findContinuousSequence(int target) { 
            int i = 1; // 滑动窗口的左边界
            int j = 1; // 滑动窗口的右边界
            int sum = 0; // 滑动窗口中数字的和
            List<int[]> resList = new ArrayList<>();
            while (i <= target / 2) { 
                if (sum < target) {  // 右边界向右移动
                    sum += j;
                    j++;
                } else if (sum > target) {  // 左边界向右移动
                    sum -= i;
                    i++;
                } else { 
                    int[] arr = new int[j - i];
                    for (int k = i; k < j; k++) { 
                        arr[k - i] = k;
                    }
                    // 左边界向右移动
                    resList.add(arr);
                    sum -= i;
                    i++;
                }
            }
            return resList.toArray(new int[resList.size()][]);
        }
    }

[Link 1]: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/e414c83ce2da4bed82a060d91e877e8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/78469b25ad914fb28a32381ffa391af1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 2]: /images/20210529/160a9801da074f28a2e69686ae452f23.png