Line data    Source code

       1              : // Copyright (c) 2024 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              : 
      17              : #include <algorithm>
      18              : #include <vector>
      19              : 
      20              : #include <gtest/gtest.h>
      21              : 
      22              : namespace {
      23              : class Solution {
      24              : public:
      25              :     // 这道题目拿到就应该想到双指针
      26            5 :     int findMax(std::vector<int> nums) {
      27            5 :         std::sort(nums.begin(), nums.end());
      28            5 :         int size = static_cast<int>(nums.size());
      29            5 :         if (nums[0] >= 0 || nums[size - 1] <= 0)
      30            2 :             return -1;
      31            3 :         int lidx = 0, ridx = size - 1;
      32            8 :         while (lidx < ridx) {
      33            7 :             int r = nums[ridx];
      34            9 :             while (lidx < ridx && nums[lidx] + r < 0)
      35            2 :                 ++lidx;
      36            7 :             if (nums[lidx] + r == 0)
      37            2 :                 return r;
      38            5 :             --ridx;
      39              :         }
      40            1 :         return -1;
      41              :     }
      42              : };
      43              : } // namespace
      44              : 
      45            4 : TEST(Leetcode, leetcode) {
      46            1 :     Solution s;
      47              :     {
      48            1 :         std::vector<int> inputs = {-1, 2, -3, 3};
      49            1 :         EXPECT_EQ(3, s.findMax(inputs));
      50            1 :     }
      51              : 
      52              :     {
      53            1 :         std::vector<int> inputs = {-1, 10, 6, 7, -7, 1};
      54            1 :         EXPECT_EQ(7, s.findMax(inputs));
      55            1 :     }
      56              : 
      57              :     {
      58            1 :         std::vector<int> inputs = {-10, 8, 6, 7, -2, -3};
      59            1 :         EXPECT_EQ(-1, s.findMax(inputs));
      60            1 :     }
      61              : 
      62              :     {
      63            1 :         std::vector<int> inputs = {-956, -831, -707};
      64            1 :         EXPECT_EQ(-1, s.findMax(inputs));
      65            1 :     }
      66              : 
      67              :     {
      68            1 :         std::vector<int> inputs = {956, 831, 707};
      69            1 :         EXPECT_EQ(-1, s.findMax(inputs));
      70            1 :     }
      71            1 : }