Line data    Source code

       1              : // Copyright (c) 2023 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : // Created: 2023/05/13 00:25
      17              : 
      18              : #include <algorithm>
      19              : #include <vector>
      20              : 
      21              : #include <gtest/gtest.h>
      22              : 
      23              : namespace {
      24              : class Solution {
      25              : public:
      26              :     // 这道题目拿到就应该想到双指针
      27            5 :     int findMax(std::vector<int> nums) {
      28            5 :         std::sort(nums.begin(), nums.end());
      29            5 :         int size = static_cast<int>(nums.size());
      30            5 :         if (nums[0] >= 0 || nums[size - 1] <= 0)
      31            2 :             return -1;
      32            3 :         int lidx = 0, ridx = size - 1;
      33            8 :         while (lidx < ridx) {
      34            7 :             int r = nums[ridx];
      35            9 :             while (lidx < ridx && nums[lidx] + r < 0)
      36            2 :                 ++lidx;
      37            7 :             if (nums[lidx] + r == 0)
      38            2 :                 return r;
      39            5 :             --ridx;
      40              :         }
      41            1 :         return -1;
      42              :     }
      43              : };
      44              : } // namespace
      45              : 
      46            4 : TEST(Leetcode, leetcode) {
      47            1 :     Solution s;
      48              :     {
      49            1 :         std::vector<int> inputs = {-1, 2, -3, 3};
      50            1 :         EXPECT_EQ(3, s.findMax(inputs));
      51            1 :     }
      52              : 
      53              :     {
      54            1 :         std::vector<int> inputs = {-1, 10, 6, 7, -7, 1};
      55            1 :         EXPECT_EQ(7, s.findMax(inputs));
      56            1 :     }
      57              : 
      58              :     {
      59            1 :         std::vector<int> inputs = {-10, 8, 6, 7, -2, -3};
      60            1 :         EXPECT_EQ(-1, s.findMax(inputs));
      61            1 :     }
      62              : 
      63              :     {
      64            1 :         std::vector<int> inputs = {-956, -831, -707};
      65            1 :         EXPECT_EQ(-1, s.findMax(inputs));
      66            1 :     }
      67              : 
      68              :     {
      69            1 :         std::vector<int> inputs = {956, 831, 707};
      70            1 :         EXPECT_EQ(-1, s.findMax(inputs));
      71            1 :     }
      72            1 : }