Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में न्यूनतम आकार उपसरणी योग


मान लीजिए हमारे पास n तत्वों की एक सरणी और एक धनात्मक पूर्णांक s है। हमें एक सन्निकट उपसरणी की न्यूनतम लंबाई ढूंढनी है जिसका योग s से बड़ा या बराबर हो। यदि ऐसी कोई उपसरणी नहीं है, तो 0 लौटाएँ।

उदाहरण: सरणी [2,3,1,2,4,3], s = 7 → आउटपुट 2 (उपसरणी [4,3] का योग 7)।

स्लाइडिंग विंडो (दो पॉइंटर्स)

  1. ans = 0, sum = 0, left = 0।
  2. right = 0 से n-1 तक:
    • sum += A[right]।
    • while sum - A[left] >= s:
      • sum -= A[left], left++।
    • यदि sum >= s:
      • ans = (ans == 0) ? (right-left+1) : min(ans, right-left+1)।
  3. ans लौटाएँ।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = 0, sum = 0, left = 0;
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum - nums[left] >= target) {
                sum -= nums[left];
                left++;
            }
            if (sum >= target) {
                if (ans == 0 || ans > right - left + 1) {
                    ans = right - left + 1;
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<int> v = {2,3,1,2,4,3};
    Solution ob;
    cout << ob.minSubArrayLen(7, v); // 2
    return 0;
}

इनपुट

7 [2,3,1,2,4,3]

आउटपुट

2
  1. - C++ में न्यूनतम पथ योग (Minimum Path Sum)

    मान लीजिए हमारे पास एक m x n मैट्रिक्स है जो गैर-ऋणात्मक पूर्णांकों से भरा है। शीर्ष बाएं कोने से नीचे दाएं कोने तक एक पथ ढूंढें जो अपने पथ के साथ सभी संख्याओं के योग को न्यूनतम करता है। गति किसी भी समय केवल नीचे या दाएं हो सकती है। उदाहरण के लिए, यदि मैट्रिक्स इस तरह है: 131 151 421 आउटपुट 7 ह

  1. - C++ में अधिकतम उपसरणी योग मॉड्यूलो m (Maximum subarray sum modulo m)

    इस समस्या में, हमें आकार n की एक सरणी और एक पूर्णांक m दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में अधिकतम उपसरणी योग मॉड्यूलो m ढूंढे। प्रोग्राम विवरण - यहां, हम उपसरणी के सभी तत्वों के योग को m से विभाजित करके प्राप्त अधिकतम मान ढूंढेंगे। आइए एक उदाहरण से समझते हैं: इनपुट - सरणी = {4

  1. - C++ में ट्रायंगल में न्यूनतम सम पथ

    समस्या कथन संख्याओं की एक त्रिकोणीय संरचना दी गई है, शीर्ष से नीचे तक न्यूनतम पथ योग ढूंढें। प्रत्येक चरण में आप नीचे की पंक्ति पर आसन्न संख्याओं पर जा सकते हैं। उदाहरण यदि इनपुट है - 5 7 3 8 1 2 9 6 4 5 तो न्यूनतम योग 13 है जैसा कि नीचे दिया गया है - 5 + 3 + 1 + 4 एल्गोरिदम डायनामिक प