在用例 [3,5,0,3,4] 中，我收到错误。这个数组如何落入 132 模式？

Question

给定一个包含 n 个整数 nums 的数组，132 模式是三个整数 nums[i]、nums[j] 和 nums[k] 的子序列，使得 i < j < k and nums[i] < nums[k] < nums[j].

如果 nums 中存在 132 模式，则返回 true，否则返回 false。 `

class Solution 
{
    public boolean find132pattern(int[] nums) 
    {
        int l = 0;
        int r = 2;
        while (r < nums.length)
        {
            int mid=(l+r)/2;
            if (nums[l] < nums[r])
            {
            if (nums[mid]>nums[r]) 
                {
                    return true;
                }
            }

            l++;
            r++;

        }

        return false;
    }
}

这是我的解决方案。如果有逻辑错误，你能帮我解决这个问题吗？

Answer 1

你的程序的问题是只有一开始就必须是

true

。

return [value]

将结束该方法，这意味着如果开始或一个部分为真，但其余部分为

false

，您的程序仍将返回

true

，因为它找到了“132”格式的一个部分。您可以尝试返回

true

，而不是在

while

循环中返回

false

:

while (r < nums.length) {
    int mid=(l+r)/2;
    if (nums[l] >= nums[r] && nums[mid] <= nums[r]) {
       return false;
    }           
    l++;
    r++;
}
return true;

这确保了如果数组条件的任何部分为假，则不会给出“误报”。

或者，您可以添加一个计数器，如下所示：

int count = l;
while (r < nums.length) {
    int mid=(l+r)/2;
    if (nums[l] < nums[r] && nums[mid] > nums[r]) {
       count++        
    }           
    l++;
    r++;
}
if (count == l) {
    return true;
}
return false;

这可确保条件始终为

true

。 然而，这两种方法的更简化版本可能就是这样做：

while (r < nums.length && (nums[l] < nums[r] && nums[mid] > nums[r])) {           
    l++;
    r++;
}
if (r == nums.length) {
    return true;
}
return false;

这会立即检查条件是否为

true

，而不需要

if

语句或其他任何内容。

我希望这有帮助！