问了问还是解决不了，我(入门)

Question

编写程序求满足1+2+3+4+…+n>=10000 的最小的正整数n为多少。

Answer 1

看到这个题目感觉有点意思，O(n)的解法容易实现，已经有其它答案写了就不再重复了。下面是用“二分查找”思想写的时间复杂度为O(log(n))的解法，仅供参考。自测输入10000的话答案是141.

public class MinN {
    public static void main(String[] args) {
        int target = 10000; //目标值
        int ans = findN(target);
        System.out.println(ans);
    }

    /**
     * 二分查找
     * */
    public static int findN(int target) {
        int i = 1,j = target;
        while (i <= j) {
            int mid = (i + j) / 2;
            long tmp = sum(1,mid);
            if(tmp >= target) {
                if(sum(1,mid) < target) {
                    return mid;
                } else {
                    j = mid - 1;
                }
            } else {
                i = mid + 1;
            }
        }
        return i;
    }

    /**
    * 求从start加到end的和。使用long类型避免计算后超出整数范围
    * */
    public static long sum(int start,int end) {
        return (long) (end - start + 1) * (long) (start + end) / 2;
    }
}