1395-count-number-of-teams.rs

// 思路：先把所有可能打印出来，再判断
pub fn num_teams_(rating: Vec<i32>) -> i32 {
    let mut res = 0;
    for first in 0..rating.len() {
        let mut first_tmp = vec!();
        first_tmp.push(rating[first]);
        for second in (first+1)..rating.len() {
            let mut second_tmp = first_tmp.clone();
            second_tmp.push(rating[second]);
            for third in (second+1)..rating.len() {
                let mut third_tmp = second_tmp.clone();
                third_tmp.push(rating[third]);
                // 至此全部组合出来了，下面判断
                if (third_tmp[0] > third_tmp[1] && third_tmp[1] > third_tmp[2]) ||
                    (third_tmp[0] < third_tmp[1] && third_tmp[1] < third_tmp[2]) {
                    res += 1;
                }
            }
        }
    }
    res
}

// 超时了  59/74 优化: 直接用指针判断
// https://leetcode-cn.com/submissions/detail/284195830/
pub fn num_teams__(rating: Vec<i32>) -> i32 {
    let mut res = 0;
    for first in 0..rating.len() {
        for second in (first+1)..rating.len() {
            for third in (second+1)..rating.len() {
                if (rating[first] > rating[second] && rating[second] > rating[third]) ||
                    (rating[first] < rating[second] && rating[second] < rating[third]) {
                    res += 1;
                }
            }
        }
    }
    res
}

// 还是超时 67/74 继续优化 ：记录第二层循环的判断，减少第三层循环的重复判断
// https://leetcode-cn.com/submissions/detail/284202564/

pub fn num_teams(rating: Vec<i32>) -> i32 {
    let mut res = 0;
    let mut trending: bool;
    for first in 0..rating.len() {
        for second in (first+1)..rating.len() {
            if rating[first] < rating[second] {
                trending = true;
            } else {
                trending = false;
            }
            for third in (second+1)..rating.len() {
                if trending {
                    if rating[second] < rating[third] {
                        res += 1;
                    }
                } else {
                    if rating[second] > rating[third] {
                        res += 1;
                    }
                }
            }
        }
    }
    res
}

fn main() {
    let rating = vec![1414,158,710,2814,965,585,620,52,2327,2390,2018,486,1166,2997,2715,336,2143,283,2705,467,381,2463,3000,703,1096,265,130,100,2194,2484,2501,1673,65,2447,663,2136,2039,2683,2093,2504,495,805,2712,512,85,1353,1520,2189,1274,1038,1829,2235,2127,2422,1569,731,469,2602,946,345,2292,2805,1579,1384,2040,921,1677,1074,814,1243,1537,2993,2596,1557,2034,2719,1185,80,1872,842,1546,1430,1212,2284,12,629,617,1661,1442,2356,1067,2632,753,1774,1848,916,728,1818,841,2804,779,280,2436,1519,1440,2291,760,2205,276,2057,563,822,707,2112,2701,113,263,164,2027,478,1705,1494,2208,1897,2352,2773,866,2725,645,1088,1361,48,2643,369,2038,2398,801,373,485,2916,2963,2467,2713,54,2396,1270,1322,2151,1046,1469,2965,1313,2191,1623,340,1299,714,851,797,2584,1016,649,2800,2911,894,930,2366,1948,2351,2223,1835,67,2512,51,1992,1903,1041,604,2401,943,2991,2367,1699,2097,671,1535,1856,1688,194,2454,2689,2718,2013,1665,2437,1823,242,719,1861,2329,2486,150,1454,2594,2192,2044,742,1629,1931,1127,64,2244,389,1698,2354,1639,2954,2700,1967,97,2174,2679,812,2024,2574,1175,1246,1236,647,1759,844,2005,35,195,1493,43,197,2310,2830,2193,2369,1044,406,1898,2211,1630,745,1297,665,2710,2442,2889,1521,2263,2011,2798,1189,2985,231,1102,2145,941,162,2478,1982,1601,1421,1918,2631,944,1220,1859,2690,219,1398,1604,1183,2121,2086,1068,1251,2111,2020,143,2844,198,1717,2957,2595,2381,1985,2851,2061,1385,1156,696,545,1203,901,1502,254,2187,1367,28,2818,1037,517,2677,134,2854,2423,1,298,2389,2008,2842,1868,302,2152,1562,754,2903,1561,1470,1943,1076,987,1578,2949,1081,2458,608,1882,1485,896,1410,2582,669,256,1913,2046,1965,272,170,1807,2471,1885,1153,1907,331,1524,989,2344,243,1177,2202,1712,1953,1054,1625,1827,2550,112,1459,1226,751,556,1933,1810,2681,2990,1465,631,2958,2824,1248,2864,1254,222,1732,501,2470,2156,687,2765,1260,2311,133,2651,1452,2334,878,2479,1125,746,23,258,1637,2142,1308,2502,1210,686,141,1990,2457,1301,2987,834,2675,1196,2264,1761,2625,2953,1422,729,1293,1172,2489,1233,1239,2724,127,2544,632,1805,2146,422,1143,2951,2564,252,2912,2350,981,1007,1373,1619,2132,172,268,1105,2138,2802,1173,300,1002,664,1320,997,1517,1352,882,2739,2728,2338,1436,446,1492,506,2559,1201,885,1111,1813,514,2424,2070,1039,59,2047,1199,2275,838,1026,1427,2259,2845,717,701,2197,1224,2462,2518,781,1668,2960,1141,1434,1008,2726,1850,1873,1779,2736,764,2238,399,2714,1735,2716,317,1832,1245,228,1474,2838,641,1020,934,2359,239,318,361,2167,1342,2721,798,2532,312,794,2393,782,1473,2915,2979,2343,802,1996,1478,1471,1816,2861,609,1193,1680,2934,2707,2590,858,1666,2099,2410,2857,156,2273,108,672,771,1504,2196,1244,677,2812,1523,534,1169,2461,658,1392,2052,1029,2466,2368,1278,2576,2200,2629,2468,1917,2823,2939,2134,642,2117,1476,1881,2460,484,261,275,1508,2503,2150,1643,2472,2165,1325,1501,1785,790,1375,1180,383,2959,2270,223,1290,148,324,1294,536,2362,2699,1603,2131,567,2635,1505];
    println!("{:?}", num_teams(rating));
}