本文共 896 字，大约阅读时间需要 2 分钟。

题目原文：

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Your algorithm should run in O(n) time complexity and O(1) space complexity. 题目大意： 给出一个数组，判断是否存在一个递增的长度为3的子序列。 题目分析： （1） 朴素解法：$O(n^3)$暴力搜索； （2） 最长递增子列：引用的方法判断最长递增子列的长度是否>=3，最好的时间复杂度是O(nlogn)。 （3） O(n)算法：扫描一遍数组，令a1是当前最小值，a2是a1以后次小值，则如果当前的数比a2还大，就存在。 源码：（language：java）

public class Solution {    public boolean increasingTriplet(int[] nums) {        int a1 = Integer.MAX_VALUE,a2 = Integer.MAX_VALUE;        for(int num : nums) {            if(num<=a1)                 a1=num;            else if(num<=a2)                a2=num;            else                return true;        }        return false;    }}

成绩：

1ms,beats 34.32%,众数1ms,65.68%

转载地址：http://ofomb.baihongyu.com/