Fair Candy Swap LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> fairCandySwap(vector<int> &aliceSizes, vector<int> &bobSizes) {
4
    sort(bobSizes.begin(), bobSizes.end());
5
    sort(aliceSizes.begin(), aliceSizes.end());
6

7
    int sum1 = 0;
8
    int sum2 = 0;
9
    vector<int> ans;
10
    for (int i = 0; i < aliceSizes.size(); i++) {
11
      sum1 += aliceSizes[i];
12
    }
13
    for (int i = 0; i < bobSizes.size(); i++) {
14
      sum2 += bobSizes[i];
15
    }
16

17
    int dif = (sum1 - sum2) / 2;
18

19
    for (int i = 0; i < aliceSizes.size(); i++) {
20
      int st = 0;
21
      int end = bobSizes.size() - 1;
22

23
      while (st <= end) {
24
        int mid = (st + end) / 2;
25

26
        if (bobSizes[mid] == aliceSizes[i] - dif) {
27
          ans.push_back(aliceSizes[i]);
28
          ans.push_back(bobSizes[mid]);
29
          return ans;
30
        }
31

32
        else if (bobSizes[mid] < aliceSizes[i] - dif) {
33
          st = mid + 1;
34
        } else if (bobSizes[mid] > aliceSizes[i] - dif) {
35
          end = mid - 1;
36
        }
37
      }
38
    }
39

40
    return ans;
41
  }
42
};