leetcode周赛---找出中枢整数

6245. 找出中枢整数
      给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：

1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。
返回中枢整数 x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。

示例 1：

输入：n = 8
输出：6
解释：6 是中枢整数，因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。
示例 2：

输入：n = 1
输出：1
解释：1 是中枢整数，因为 1 = 1 。
示例 3：

输入：n = 4
输出：-1
解释：可以证明不存在满足题目要求的整数。

提示：

1 <= n <= 1000

解法一 C++

class Solution {
public:
    int pivotInteger(int n) {
        if(n==1){
            return 1;
        }
        int start = 1, end = n;
        int sumStart=1, sumEnd=n;
        while(start < end){
            // 对左边累加求和
            while((sumStart <sumEnd)&&(start<end)){
                start ++;
                sumStart += start;
            }
            //对右边累加求和
            while((sumStart > sumEnd)&&(start<end)){
                end --;
                sumEnd += end;
            }
            //判断是否存在中枢整数
            if((sumStart == sumEnd)&&(start==end-2)){
                return end-1;
            }
            //对提前出现累加求和相等情况做处理
            if((sumStart == sumEnd)&&(start!=end-2)){
                end--;
                start ++;
                sumStart += start;
                sumEnd += end;
            }                                                                                                                     
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

解法二 golang

func pivotInteger(n int) int {
    if n == 1{
        return 1
    }
    start := 1
    end := n
    sumStart := 1
    sumEnd := n
    for{
        if start>=end{
            break
        }
        if start < end{
        	// 对左边累加求和
            for{
                if((sumStart <sumEnd)&&(start<end)){
                    start += 1;
                    sumStart += start;
                }
                if((sumStart >= sumEnd)||(start>=end)){
                    break
                }
            }
            //对右边累加求和
            for{
                if((sumStart > sumEnd)&&(start<end)){
                    end --;
                    sumEnd += end;
                }
                if((sumStart <= sumEnd)||(start>=end)){
                    break
                }
            }
            if((sumStart == sumEnd)&&(start==end-2)){
                return end-1
            }
            //对提前出现累加求和相等情况做处理
            if((sumStart == sumEnd)&&(start!=end-2)){
                end--
                start ++
                sumStart += start
                sumEnd += end
            }            
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

###解法三 python

class Solution(object):
    def pivotInteger(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        start, end, sumStart, sumEnd = 1, n, 1, n
        while start < end:
            while sumStart < sumEnd and start < end:
                start += 1
                sumStart += start
            while sumStart > sumEnd and start < end:
                end -= 1
                sumEnd += end
            if sumStart == sumEnd and end-2 == start:
                return end-1
            if sumStart == sumEnd and end-2 != start:
                start += 1
                sumStart += start
                end -= 1
                sumEnd += end
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24